shm/Project4/vptr_manager.h

/*
 * Copyright 2020 ByteDance Games, Inc. All Rights Reserved.
 *
 * Author: Liuziming <liuziming.kelvin@bytedance.com>
 */

#pragma once

#include <stddef.h>
#include <string.h>
#include <string>
#include <vector>
#include <typeinfo>
#include <unordered_map>

#include "shm_helper.h"
# if defined(__GNUC__)
#include <tr2/type_traits>
#include <typeinfo>
#include <map>
#ifdef OUTPUT_BASES
extern std::map<std::string, std::vector<std::string>> g_bases_name;
#endif
#else 
#include "type_helper.h"
#define REINTERPRET_CAST_TAG	
#endif

namespace bg
{
	namespace detail
	{

		struct BaseTypeInfo
		{
			TypeName type;
			ptrdiff_t offset;

			BaseTypeInfo(const char* type, ptrdiff_t offset) : type(type), offset(offset) {}
		};

		class VptrObjectContainerBase
		{
		public:
			VptrObjectContainerBase(const TypeName& type, bool in_shm);
			virtual ~VptrObjectContainerBase();

			virtual void FixObjects() = 0;
			virtual VptrObjectContainerBase* ShmNew() = 0;

			void FixVptr();
			const TypeName& GetTypeName() const { return m_type; }
			const BaseTypeInfo* GetBaseTypeInfo(const TypeName& base_type);

			void RecordObject(void* ptr);
			void RemoveObject(void* ptr);

		protected:
			bool FixSelf();
			void DoRemoveObject(size_t index);

		protected:
			static constexpr const double EXPANSION_FACTOR = 1.5;

			uint64_t m_version = 0;
			TypeName m_type;
			// As we have containers both in normal memory and shared
			// memory, so we make the pointer container as pointer here,
			// only initialize it when it's used in shared memory.
			std::vector<void*, ShmAllocator<void*>>* m_objects = nullptr;
			// The following field is initialized in derived class constructor.
			std::vector<BaseTypeInfo>* m_base_types = nullptr;
		};

		template<typename T>
		class VptrObjectContainer final : public VptrObjectContainerBase
		{
		public:
			static const T static_object;
			static const VptrObjectContainer<T> static_container;

			/*
			 * NOTE: The 2nd arg to `TypeName(...)` MUST BE 0 here, because when
			 * we delete a pointer of polymorphic type, we can only know it's real
			 * type with `typeid(*ptr).name()`, but we cannot get the size of that
			 * real type, so we have to abandon size here, to match the info we can
			 * get at deletion. The same as following calls to this function.
			 */
			VptrObjectContainer() : VptrObjectContainerBase(TypeName(typeid(T).name()), false)
			{
				SHM_DEBUG_ASSERT(this == &static_container);

				size_t count = GetBaseClassCount();
				if(count > 0)
				{
					m_base_types = new std::vector<BaseTypeInfo>();
					m_base_types->reserve(count);
					FillBaseTypeInfo(m_base_types, Index2Type<0>());
				}
			}

			VptrObjectContainer(const VptrObjectContainer& that) : VptrObjectContainerBase(that.m_type, true)
			{
				SHM_DEBUG_ASSERT(&that == &static_container);
			}

			~VptrObjectContainer() final = default;

			void FixObjects() final
			{
				SHM_TRACE(">>>>> fixing vptr of objects in container(%p: %s)...", this, m_type.c_str());
				for(void* ptr : *m_objects)
				{
					DoFix(ptr, std::integral_constant<bool, GetBaseClassCount() != 0>(), Index2Type<0>());
				}
				SHM_TRACE("<<<<< vptr of objects in container(%p: %s) fixed.", this, m_type.c_str());
			}

			VptrObjectContainerBase* ShmNew() final
			{
				SHM_DEBUG_ASSERT(this == &static_container);
				ShmAllocator<VptrObjectContainer<T>> allocator;
				VptrObjectContainer<T>* ptr = allocator.allocate(1);
				if(SHM_LIKELY(ptr))
				{
					allocator.construct(ptr, *this);
				}

				return ptr;
			}

		private:
			template<typename... Types>
			struct List
			{
				static constexpr size_t count = sizeof...(Types);
			};

			template<typename NewType, typename List>
			struct PrependList;

			template<typename NewType, typename... Types>
			struct PrependList<NewType, List<Types...>>
			{
				using ListType = List<NewType, Types...>;
			};

			template<typename List>
			struct RemoveFirst;

			template<typename Head, typename... Rest>
			struct RemoveFirst<List<Head, Rest...>>
			{
				using RestList = List<Rest...>;
			};

			struct NullType {};

			template<typename T>
			struct bases
			{
				typedef __reflection_typelist<>		type;
			};

			template<typename Type>
# if defined(__GNUC__)
			using RefList = typename std::tr2::bases<Type>::type;
#elif defined(_MSC_VER)
			using RefList = typename bases<Type>::type;

#endif


			template<bool empty, typename RefList>
			struct DoMakeList;

			template<typename RefList>
			struct DoMakeList<true, RefList>
			{
				using ListType = List<NullType>;
			};

			template<typename RefList>
			struct DoMakeList<false, RefList>
			{
				using ListType =
					typename PrependList<
					typename RefList::first::type,
					typename DoMakeList<
					RefList::rest::type::empty::value,
					typename RefList::rest::type
					>::ListType
					>::ListType;
			};

			template<typename Type>
			struct MakeList
			{
				using Result =
					typename DoMakeList<
					RefList<Type>::empty::value,
					RefList<Type>
					>::ListType;
			};

			template<size_t N, typename BaseList>
			struct GetNthBaseClass;

			template<size_t N, typename Head, typename... Rest>
			struct GetNthBaseClass<N, List<Head, Rest...>>
			{
				using BaseType = typename GetNthBaseClass<N - 1, List<Rest...>>::BaseType;
			};

			template<typename Head, typename... Rest>
			struct GetNthBaseClass<0, List<Head, Rest...>>
			{
				using BaseType = Head;
			};
# if defined(__GNUC__)
			template<typename Derived, typename Base>
			struct BaseClassOffset
			{

				static constexpr const Derived* derived = &VptrObjectContainer<T>::static_object;
				static constexpr const Base* base = static_cast<const Base*>(derived);

				static REINTERPRET_CAST_TAG  ptrdiff_t value;

				static constexpr ptrdiff_t value =
					reinterpret_cast<intptr_t>(base) - reinterpret_cast<intptr_t>(derived);


				/*
				 * This does not work with higher GCC version, due to C++ 11 standard specifies
				 * that `reinterpret_cast` cannot be used inside constexpr expression. See this
				 * link for detail:
				 * https://stackoverflow.com/questions/24398102/constexpr-and-initialization-of-a-static-const-void-pointer-with-reinterpret-cas
				 *
				 * static constexpr ptrdiff_t value =
				 *     reinterpret_cast<intptr_t>(static_cast<Base*>(static_cast<Derived*>(0) + 1)) -
				 *     reinterpret_cast<intptr_t>(static_cast<Derived*>(0) + 1);
				 */
			};
#endif
			template<size_t N>
# if defined(__GNUC__)
			static constexpr ptrdiff_t GetBaseClassOffset()
			{
				using BaseList = typename MakeList<T>::Result;
				using BaseType = typename GetNthBaseClass<N, BaseList>::BaseType;

				return BaseClassOffset<T, BaseType>::value;
			}
#else
			static REINTERPRET_CAST_TAG ptrdiff_t GetBaseClassOffset()
			{
				using BaseList = typename MakeList<T>::Result;
				using BaseType = typename GetNthBaseClass<N, BaseList>::BaseType;
				static constexpr const T* derived = &VptrObjectContainer<T>::static_object;
				static constexpr const BaseType* base = static_cast<const BaseType*>(derived);

				return reinterpret_cast<intptr_t>(base) - reinterpret_cast<intptr_t>(derived);
			}
#endif

			static constexpr size_t GetBaseClassCount()
			{
				// There is a NullType at the end of the list, so we compare with 1 here
				static_assert(MakeList<T>::Result::count >= 1, "Invalid base class count");
				return MakeList<T>::Result::count - 1;
			}

			/*
			 * The BEST solution should be the following:
			 *   Generate an base class offset array at compile time, during fixing, iterate
			 *   over the array and fix each vptr at corresponding offset. However, there is
			 *   a bug in GCC(4.8), which leads to the following code cannot compile:
			 *
			 *     internal compiler error: in convert_nontype_argument, at cp/pt.c:5623
			 *     Please submit a full bug report.
			 *     ...
			 *
			 *   So, we have to use template function specialization instead to solve this
			 *   problem without a lot of ugly macro definitions.
			 *
			 *
			 * template<ptrdiff_t... offsets>
			 * struct OffsetHolder {
			 *     static constexpr ptrdiff_t base_offsets[sizeof...(offsets)] = { offsets... };
			 * };
			 *
			 * template<size_t total, typename BaseList, ptrdiff_t... offsets>
			 * struct DoGenerateOffsets {
			 *     using Result = typename DoGenerateOffsets<
			 *         total,
			 *         typename RemoveFirst<BaseList>::Rest,
			 *         // There is a NullType at the end of the list, we should make
			 *         // this consistent with value defined in GetBaseClassCount()
			 *         GetBaseClassOffset<total - (BaseList::count - 1)>(),
			 *         offsets...
			 *     >::Result;
			 * };
			 *
			 * template<size_t total, ptrdiff_t... offsets>
			 * struct DoGenerateOffsets<total, List<NullType>, offsets...> {
			 *     using Result = OffsetHolder<offsets...>;
			 * };

			 * struct GenerateOffsets {
			 *     using Result = typename DoGenerateOffsets<
			 *         GetBaseClassCount(), typename MakeList<T>::Result
			 *     >::Result;
			 * };
			 *
			 * void DoFix(void *ptr) {
			 *     using OffsetArray = GenerateOffsets::Result;
			 *     for (size_t i = 0; i < ARRAY_SIZE(OffsetArray::base_offsets); ++i) {
			 *         const ptrdiff_t offset = OffsetArray::base_offsets[i];
			 *         // do fix vptr here
			 *     }
			 * }
			 *
			 */

			template<size_t>
			struct Index2Type {};

			template<size_t index>
			void FillBaseTypeInfo(std::vector<BaseTypeInfo>* base_types, Index2Type<index>)
			{
				using BaseList = typename MakeList<T>::Result;
				using BaseType = typename GetNthBaseClass<index, BaseList>::BaseType;
				static constexpr const ptrdiff_t offset = GetBaseClassOffset<index>();
				static_assert(offset >= 0, "invalid offset");

				BaseTypeInfo info(typeid(BaseType).name(), offset);
				base_types->push_back(info);
				FillBaseTypeInfo(base_types, Index2Type<index + 1>());
			}

			void FillBaseTypeInfo(std::vector<BaseTypeInfo>*, Index2Type<GetBaseClassCount()>) {}

			// This function means there is no base class for class T.
			void DoFix(void* ptr, std::false_type, Index2Type<0>)
			{
				static constexpr const T* t = &static_object;

				const uintptr_t* new_vptr = reinterpret_cast<const uintptr_t*>(reinterpret_cast<const char*>(t));
				uintptr_t* old_vptr = reinterpret_cast<uintptr_t*>(reinterpret_cast<char*>(ptr));

				if(!HasVptr<T>::value)
				{
					SHM_ERROR("object(%p), type(%s), no base type, vptr not found(%#lx : %#lx), at least one virtual function is required.",
							  ptr, m_type.c_str(), *old_vptr, *new_vptr);
					return;
				}

				SHM_DEBUG("object(%p), type(%s), no base type, old vptr(%#lx), new vptr(%#lx)", ptr, m_type.c_str(), *old_vptr, *new_vptr);
				if(*old_vptr != *new_vptr)
				{
					*old_vptr = *new_vptr;
				}
			}

			template<size_t index>
			void DoFix(void* ptr, std::true_type, Index2Type<index>)
			{
				using BaseList = typename MakeList<T>::Result;
				using BaseType = typename GetNthBaseClass<index, BaseList>::BaseType;

				static constexpr const ptrdiff_t offset = GetBaseClassOffset<index>();
				static constexpr const T* t = &static_object;

				const uintptr_t* new_vptr = reinterpret_cast<const uintptr_t*>(reinterpret_cast<const char*>(t) + offset);
				uintptr_t* old_vptr = reinterpret_cast<uintptr_t*>(reinterpret_cast<char*>(ptr) + offset);

				TypeName base_type(typeid(BaseType).name());
				if(!HasVptr<BaseType>::value)
				{
					SHM_ERROR("object(%p), type(%s), base type(%s), base index(%lu锛? offset(%#lx), vptr(%#lx : %#lx) not found, a virtual destructor is recommended.",
							  ptr, m_type.c_str(), base_type.c_str(), index, offset, *old_vptr, *new_vptr);
				}
				else
				{
					SHM_DEBUG("object(%p), type(%s), base type(%s), base index(%lu锛? offset(%#lx), old vptr(%#lx), new vptr(%#lx)",
							  ptr, m_type.c_str(), base_type.c_str(), index, offset, *old_vptr, *new_vptr);

					if(*old_vptr != *new_vptr)
					{
						*old_vptr = *new_vptr;
					}
				}

				DoFix(ptr, std::true_type(), Index2Type<index + 1>());
			}

			void DoFix(void*, std::true_type, Index2Type<GetBaseClassCount()>) {}
		};
		//template<typename T> const T VptrObjectContainer<T>::static_object = T();
		template<typename T> const T VptrObjectContainer<T>::static_object;
		template<typename T> const VptrObjectContainer<T> VptrObjectContainer<T>::static_container;

		class VptrManager
		{
		public:
			static bool Init();
			static void Fini();
			~VptrManager();

			template<typename T, typename... Args>
			static T* NewVptrObject(Args&&... args)
			{
				return NewVptrObjectExtraSpace<T>(0, std::forward<Args>(args)...);
			}

			template<typename T, typename... Args>
			static T* NewVptrObjectExtraSpace(size_t extra_space, Args&&... args)
			{
				static_assert(HasVptr<T>::value, "type must be polymorphic or have vptr at least!");
				const TypeName& type = VptrObjectContainer<T>::static_container.GetTypeName();

				// Do not use static assertion here, sometimes it might not need a virtual destructor.
				// static_assert(std::has_virtual_destructor<T>::value, "polymorphic type must have a virtual destructor!");
				if(!std::has_virtual_destructor<T>::value)
				{
					SHM_ERROR("it's better to declare destructor virtual for polymorphic type(%s).", type.c_str());
				}

				void* ptr = NewSpace(sizeof(T) + extra_space);
				if(SHM_LIKELY(ptr))
				{
					new (ptr) T(std::forward<Args>(args)...);
					RecordObject(type, ptr);
				}

				return static_cast<T*>(ptr);
			}

			template<typename T>
			static void DelVptrObject(T* ptr)
			{
				static_assert(HasVptr<T>::value, "type must be polymorphic or have vptr at least!");

				if(SHM_LIKELY(ptr))
				{
					TypeName base_type(typeid(T).name());
					TypeName real_type(typeid(*ptr).name());

					void* real_ptr = GetRealPtr(base_type, real_type, ptr);
					RemoveObject(real_type, real_ptr);
					ptr->~T();
					FreeSpace(real_ptr);
				}
			}

			static void FixVptr();

		private:
			static void* NewSpace(size_t bytes);
			static void FreeSpace(void* ptr);
			static void* GetRealPtr(const TypeName& base_type, const TypeName& real_type, void* ptr);
			static void RecordObject(const TypeName& type, void* ptr);
			static void RemoveObject(const TypeName& type, void* ptr);

		private:
			template<typename Key, typename Value, typename Hash = std::hash<Key>, typename Pred = std::equal_to<Key>>
			using Container = std::unordered_map<Key, Value, Hash, Pred, ShmAllocator<std::pair<const Key, Value>>>;
			Container<TypeName, VptrObjectContainerBase*, TypeNameHasher> m_type_to_containers;
		};

	} // namespace detail
} // namespace bg