Main Page   Reference Manual   Namespace List   Compound List   Namespace Members   Compound Members   File Members  

private_allocator.h

Go to the documentation of this file.
00001 // $Header: /cvsroot/libcwd/libcwd/include/libcwd/private_allocator.h,v 1.16 2005/12/24 00:13:52 libcw Exp $
00002 //
00003 // Copyright (C) 2001 - 2004, by
00004 // 
00005 // Carlo Wood, Run on IRC <carlo@alinoe.com>
00006 // RSA-1024 0x624ACAD5 1997-01-26                    Sign & Encrypt
00007 // Fingerprint16 = 32 EC A7 B6 AC DB 65 A6  F6 F6 55 DD 1C DC FF 61
00008 //
00009 // This file may be distributed under the terms of the Q Public License
00010 // version 1.0 as appearing in the file LICENSE.QPL included in the
00011 // packaging of this file.
00012 //
00013 
00018 #ifndef LIBCWD_PRIVATE_ALLOCATOR_H
00019 #define LIBCWD_PRIVATE_ALLOCATOR_H
00020 
00021 #ifndef LIBCWD_CONFIG_H
00022 #include <libcwd/config.h>
00023 #endif
00024 
00025 #if CWDEBUG_ALLOC               // This file is not used when --disable-alloc was used.
00026 
00027 #ifndef LIBCWD_PRIVATE_MUTEX_INSTANCES_H
00028 #include <libcwd/private_mutex_instances.h>
00029 #endif
00030 #ifndef LIBCWD_CORE_DUMP_H
00031 #include <libcwd/core_dump.h>
00032 #endif
00033 #ifndef LIBCW_CSTDDEF
00034 #define LIBCW_CSTDDEF
00035 #include <cstddef>                      // Needed for size_t
00036 #endif
00037 #if __GNUC__ > 3 && LIBCWD_THREAD_SAFE
00038 #include <libcwd/private_mutex.h>       // mutex_ct
00039 #endif
00040 #include <memory>
00041 
00042 //===================================================================================================
00043 // Allocators
00044 //
00045 //
00046 
00047 /* The allocators used by libcwd have the following characteristics:
00048 
00049    1) The type T that is being allocated and deallocated.
00050    2) Whether or not the allocation is internal, auto-internal or in userspace.
00051    3) The pool instance from which the allocation should be drawn.
00052    4) Whether or not a lock is needed for this pool.
00053    5) Whether or not this allocation belongs to a libcwd
00054       critical area and if so, which one.
00055 
00056    Note that each critical area (if any) uses its own lock and
00057    therefore no (additional) lock will be needed for the allocator.
00058    Otherwise a lock is always needed (in the multi-threaded case).
00059    As of gcc 4.0, the used pool allocator doesn't use locks anymore
00060    but separates the pools per thread (except for one common pool),
00061    this need is equivalent for us to needing a lock or not: if we
00062    don't need a lock then there is also no need to separate per thread.
00063 
00064    There are five different allocators in use by libcwd:
00065 
00066 Multi-threaded case:
00067 
00068    Allocator name               | internal | Pool instance                      | Needs lock
00069    ----------------------------------------------------------------------------------------------------
00070    memblk_map_allocator         | yes      | memblk_map_instance                | no (memblk_map_instance critical area)
00071    object_files_allocator       | yes      | object_files_instance              | no (object_files_instance critical area)
00072    internal_allocator           | yes      | multi_threaded_internal_instance   | yes
00073    auto_internal_allocator      | auto     | multi_threaded_internal_instance   | yes
00074    userspace_allocator          | no       | userspace_instance                 | yes
00075 
00076 Single-threaded case:
00077 
00078    Allocator name               | internal | Pool instance                      | Needs lock
00079    ----------------------------------------------------------------------------------------------------
00080    memblk_map_allocator         | yes      | single_threaded_internal_instance  | no
00081    object_files_allocator       | yes      | single_threaded_internal_instance  | no
00082    internal_allocator           | yes      | single_threaded_internal_instance  | no
00083    auto_internal_allocator      | auto     | single_threaded_internal_instance  | no
00084    userspace_allocator          | no       | std::alloc                         | -
00085 
00086 */
00087 
00088 #if __GNUC__ == 3 && __GNUC_MINOR__ == 4
00089 #include <ext/pool_allocator.h>         // __gnu_cxx::__pool_alloc
00090 #endif
00091 
00092 namespace libcwd {
00093   namespace _private_ {
00094 
00095 // This is a random number in the hope nobody else uses it.
00096 int const random_salt = 327665;
00097 
00098 // Dummy mutex instance numbers, these must be negative.
00099 int const multi_threaded_internal_instance = -1;
00100 int const single_threaded_internal_instance = -2;
00101 int const userspace_instance = -3;
00102 
00103 // Definition of CharPoolAlloc.
00104 #if __GNUC__ == 3 && __GNUC_MINOR__ < 4
00105 template<bool needs_lock, int pool_instance>
00106   struct CharPoolAlloc : public std::__default_alloc_template<needs_lock, random_salt + pool_instance> {
00107     typedef char* pointer;
00108   };
00109 #elif __GNUC__ == 3 && __GNUC_MINOR__ == 4 && __GNUC_PATCHLEVEL__ == 0
00110 template<bool needs_lock, int pool_instance>
00111   struct CharPoolAlloc : public __gnu_cxx::__pool_alloc<needs_lock, random_salt + pool_instance> {
00112     typedef char* pointer;
00113   };
00114 #elif __GNUC__ == 3
00115 // gcc 3.4.1 and higher.
00116 template<int pool_instance>
00117   struct char_wrapper {
00118     char c;
00119   };
00120 // gcc 3.4.1 and 3.4.2 always use a lock, in the threaded case.
00121 template<bool needs_lock, int pool_instance>
00122   class CharPoolAlloc : public __gnu_cxx::__pool_alloc<char_wrapper<pool_instance> > { };
00123 #else // gcc 4.0 and higher.
00124 // Sometimes reusing code isn't possibly anymore (die gcc developers die).
00125 
00126 static size_t const maximum_size_exp = 10;                      // The log2 of the maximum size that is
00127                                                                 // allocated in a pool. Larger sizes are
00128                                                                 // allocated directly with operator new.
00129 static size_t const maximum_size = (1U << maximum_size_exp);    // 1024 bytes.
00130 
00131 struct Node {
00132   Node* M_next;
00133   Node* M_prev;
00134 
00135   Node* next(void) const { return M_next; }
00136   Node* prev(void) const { return M_prev; }
00137 
00138   void unlink(void)
00139   {
00140     M_prev->M_next = M_next;
00141     M_next->M_prev = M_prev;
00142   }
00143 };
00144 
00145 // The log2 of minimum_size. 2^(minimum_size_exp - 1) < sizeof(Node) <= 2^minimum_size_exp.
00146 template <unsigned int N> struct log2 { enum { result = 1 + log2<N/2>::result }; };
00147 template<> struct log2<0> { enum { result = -1 }; };
00148 static size_t const minimum_size_exp = log2<sizeof(Node) - 1>::result + 1;      // Calculate rounded up log2 value.
00149 
00150 static size_t const minimum_size = (1U << minimum_size_exp);    // The minimum chunk size, must be a power of 2.
00151 // The number of different buckets (with repsective chunk sizes: 8, 16, 32, 64, 128, 256, 512 and 1024).
00152 static int const bucket_sizes = maximum_size_exp - minimum_size_exp + 1;
00153 
00154 struct List : public Node {
00155   bool empty(void) const { return M_next == this; }
00156   void insert(Node* node)
00157   {
00158     node->M_prev = this;
00159     node->M_next = M_next;
00160     M_next->M_prev = node;
00161     M_next = node;
00162   }
00163   void insert_back(Node* node)
00164   {
00165     node->M_prev = M_prev;
00166     node->M_next = this;
00167     M_prev->M_next = node;
00168     M_prev = node;
00169   }
00170 private:
00171   using Node::next;
00172   using Node::prev;
00173 };
00174 
00175 struct ChunkNode : public Node {
00176   // This is commented out because it's 'virtual' (it can be zero size too).
00177   // char M_padding[size_of(ChunkNode) - sizeof(Node)];
00178 
00179   ChunkNode* next(void) const { return static_cast<ChunkNode*>(M_next); }
00180   ChunkNode* prev(void) const { return static_cast<ChunkNode*>(M_prev); }
00181 };
00182 
00183 struct ChunkList : public List {
00184   unsigned int M_used_count;    // Number of _used_ chunks (thus, that are allocated and not in the list anymore).
00185   ChunkNode* begin(void) const { return static_cast<ChunkNode*>(M_next); }
00186   Node const* end(void) const { return this; }
00187 };
00188 
00189 struct BlockNode : public Node {
00190   ChunkList M_chunks;
00191   ChunkNode M_data[1];          // One or more Chunks.
00192 
00193   BlockNode* next(void) const { return static_cast<BlockNode*>(M_next); }
00194   BlockNode* prev(void) const { return static_cast<BlockNode*>(M_prev); }
00195 };
00196 
00197 struct BlockList : public List {
00198   unsigned int* M_count_ptr;    // Pointer to number of blocks (thus, that are in the (full+notfull) list).
00199   unsigned short M_internal;    // Whether or not this block list contains internal blocks or not.
00200 
00201   BlockNode* begin(void) const { return static_cast<BlockNode*>(M_next); }
00202   Node const* end(void) const { return this; }
00203 
00204   void initialize(unsigned int* count_ptr, unsigned short internal);
00205   void uninitialize(void);
00206   ~BlockList() { uninitialize(); }
00207 #if CWDEBUG_DEBUG
00208   void consistency_check(void);
00209 #endif
00210 };
00211 
00212 struct TSD_st;
00213 
00214 struct FreeList {
00215 #if LIBCWD_THREAD_SAFE
00216   pthread_mutex_t M_mutex;
00217 #endif
00218   bool M_initialized;
00219   unsigned int M_count[bucket_sizes];           // Number of blocks (in the full+notfull list).
00220   unsigned short M_keep[bucket_sizes];          // Number of blocks that shouldn't be freed.
00221   BlockList M_list_notfull[bucket_sizes];
00222   BlockList M_list_full[bucket_sizes];
00223 
00224 #if LIBCWD_THREAD_SAFE
00225   void initialize(TSD_st& __libcwd_tsd);
00226 #else
00227   void initialize(void);
00228 #endif
00229   void uninitialize(void);
00230   ~FreeList() { uninitialize(); }
00231   char* allocate(int power, size_t size);
00232   void deallocate(char* p, int power, size_t size);
00233 #if CWDEBUG_DEBUG
00234   void consistency_check(void);
00235 #endif
00236 };
00237 
00238 template<bool needs_lock, int pool_instance>
00239   class CharPoolAlloc {
00240   private:
00241     static FreeList S_freelist;
00242 
00243   public:
00244     // Type definitions.
00245     typedef char        value_type;
00246     typedef size_t      size_type;
00247     typedef ptrdiff_t   difference_type;
00248     typedef char*       pointer;
00249     typedef char const* const_pointer;
00250     typedef char&       reference;
00251     typedef char const& const_reference;
00252 
00253     // Allocate but don't initialize num elements of type T.
00254 #if LIBCWD_THREAD_SAFE
00255     pointer allocate(size_type num, TSD_st&);
00256 #else
00257     pointer allocate(size_type num);
00258 #endif
00259 
00260     // Deallocate storage p of deleted elements.
00261 #if LIBCWD_THREAD_SAFE
00262     void deallocate(pointer p, size_type num, TSD_st&);
00263 #else
00264     void deallocate(pointer p, size_type num);
00265 #endif
00266 
00267     template <bool needs_lock1, int pool_instance1,
00268               bool needs_lock2, int pool_instance2>
00269       friend inline
00270       bool operator==(CharPoolAlloc<needs_lock1, pool_instance1> const&,
00271                       CharPoolAlloc<needs_lock2, pool_instance2> const&);
00272     template <bool needs_lock1, int pool_instance1,
00273               bool needs_lock2, int pool_instance2>
00274       friend inline
00275       bool operator!=(CharPoolAlloc<needs_lock1, pool_instance1> const&,
00276                       CharPoolAlloc<needs_lock2, pool_instance2> const&);
00277   };
00278 #endif // gcc 4.0 and higher.
00279 
00280 // Convenience macros.
00281 #if CWDEBUG_DEBUG
00282 #define LIBCWD_COMMA_INT_INSTANCE , int instance
00283 #define LIBCWD_COMMA_INSTANCE , instance
00284 #define LIBCWD_DEBUGDEBUG_COMMA(x) , x
00285 #else
00286 #define LIBCWD_COMMA_INT_INSTANCE
00287 #define LIBCWD_COMMA_INSTANCE
00288 #define LIBCWD_DEBUGDEBUG_COMMA(x)
00289 #endif
00290 
00291 enum pool_nt {
00292   userspace_pool,
00293   internal_pool,
00294   auto_internal_pool
00295 };
00296 
00297 // This wrapper adds sanity checks to the allocator use (like testing if
00298 // 'internal' allocators are indeed only used while in internal mode, and
00299 // critical area allocators are only used when the related lock is indeed
00300 // locked etc.
00301 template<typename T, class CharAlloc, pool_nt internal LIBCWD_COMMA_INT_INSTANCE>
00302     class allocator_adaptor {
00303     private:
00304       // The underlying allocator.
00305       CharAlloc M_char_allocator;
00306 
00307     public:
00308       // Type definitions.
00309       typedef T         value_type;
00310       typedef size_t    size_type;
00311       typedef ptrdiff_t difference_type;
00312       typedef T*                pointer;
00313       typedef T const*  const_pointer;
00314       typedef T&                reference;
00315       typedef T const&  const_reference;
00316 
00317       // Rebind allocator to type U.
00318       template <class U>
00319         struct rebind {
00320           typedef allocator_adaptor<U, CharAlloc, internal LIBCWD_COMMA_INSTANCE> other;
00321         };
00322 
00323       // Return address of values.
00324       pointer address(reference value) const { return &value; }
00325       const_pointer address(const_reference value) const { return &value; }
00326 
00327       // Constructors and destructor.
00328       allocator_adaptor(void) throw() { }
00329       allocator_adaptor(allocator_adaptor const& a) : M_char_allocator(a.M_char_allocator) { }
00330       template<class U>
00331         allocator_adaptor(allocator_adaptor<U, CharAlloc, internal LIBCWD_COMMA_INSTANCE> const& a) :
00332             M_char_allocator(a.M_char_allocator) { }
00333       template<class T2, class CharAlloc2, pool_nt internal2 LIBCWD_DEBUGDEBUG_COMMA(int instance2)>
00334         friend class allocator_adaptor;
00335       ~allocator_adaptor() throw() { }
00336 
00337       // Return maximum number of elements that can be allocated.
00338       size_type max_size(void) const { return M_char_allocator.max_size() / sizeof(T); }
00339 
00340       // Allocate but don't initialize num elements of type T.
00341       pointer allocate(size_type num);
00342       pointer allocate(size_type num, void const* hint);
00343 
00344       // Deallocate storage p of deleted elements.
00345       void deallocate(pointer p, size_type num);
00346 
00347       // Initialize elements of allocated storage p with value value.
00348       void construct(pointer p, T const& value) { new ((void*)p) T(value); }
00349 
00350       // Destroy elements of initialized storage p.
00351       void destroy(pointer p) { p->~T(); }
00352 
00353 #if CWDEBUG_DEBUG || CWDEBUG_DEBUGM
00354     private:
00355       static void sanity_check(void);
00356 #endif
00357 
00358       template <class T1, class CharAlloc1, pool_nt internal1 LIBCWD_DEBUGDEBUG_COMMA(int inst1),
00359                 class T2, class CharAlloc2, pool_nt internal2 LIBCWD_DEBUGDEBUG_COMMA(int inst2)>
00360         friend inline
00361         bool operator==(allocator_adaptor<T1, CharAlloc1, internal1 LIBCWD_DEBUGDEBUG_COMMA(inst1)> const& a1,
00362                         allocator_adaptor<T2, CharAlloc2, internal2 LIBCWD_DEBUGDEBUG_COMMA(inst2)> const& a2);
00363       template <class T1, class CharAlloc1, pool_nt internal1 LIBCWD_DEBUGDEBUG_COMMA(int inst1),
00364                 class T2, class CharAlloc2, pool_nt internal2 LIBCWD_DEBUGDEBUG_COMMA(int inst2)>
00365         friend inline
00366         bool operator!=(allocator_adaptor<T1, CharAlloc1, internal1 LIBCWD_DEBUGDEBUG_COMMA(inst1)> const& a1,
00367                         allocator_adaptor<T2, CharAlloc2, internal2 LIBCWD_DEBUGDEBUG_COMMA(inst2)> const& a2);
00368     };
00369 
00370 #if LIBCWD_THREAD_SAFE
00371 // We normally would be able to use the default allocator, but... libcwd functions can
00372 // at all times be called from malloc which might be called from std::allocator with its
00373 // lock set.  Therefore we also use a separate allocator pool for the userspace, in the
00374 // threaded case.
00375 #define LIBCWD_CHARALLOCATOR_USERSPACE(instance) ::libcwd::_private_::                          \
00376         allocator_adaptor<char,                                                                 \
00377                           CharPoolAlloc<true, userspace_instance>,                              \
00378                           userspace_pool                                                        \
00379                           LIBCWD_DEBUGDEBUG_COMMA(::libcwd::_private_::instance)>
00380 #endif
00381 
00382 // Both, multi_threaded_internal_instance and memblk_map_instance use also locks for
00383 // the allocator pool itself because they (the memory pools) are being shared between
00384 // threads from within critical areas with different mutexes.
00385 // Other instances (> 0) are supposed to only use the allocator instance from within
00386 // the critical area of the corresponding mutex_tct<instance>, and thus only by one
00387 // thread at a time.
00388 #if LIBCWD_THREAD_SAFE
00389 #define LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance)                                              \
00390                                 ::libcwd::_private_::instance ==                                \
00391                                 ::libcwd::_private_::multi_threaded_internal_instance ||        \
00392                                 ::libcwd::_private_::instance ==                                \
00393                                 ::libcwd::_private_::memblk_map_instance
00394 #else // !LIBCWD_THREAD_SAFE
00395 #define LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance) false
00396 #endif // !LIBCWD_THREAD_SAFE
00397 
00398 #define LIBCWD_CHARALLOCATOR_INTERNAL(instance) ::libcwd::_private_::                   \
00399         allocator_adaptor<char,                                                                 \
00400                           CharPoolAlloc<LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance),             \
00401                                         ::libcwd::_private_::instance >,                        \
00402                           internal_pool                                                         \
00403                           LIBCWD_DEBUGDEBUG_COMMA(::libcwd::_private_::instance)>
00404 
00405 #define LIBCWD_CHARALLOCATOR_AUTO_INTERNAL(instance) ::libcwd::_private_::              \
00406         allocator_adaptor<char,                                                                 \
00407                           CharPoolAlloc<LIBCWD_ALLOCATOR_POOL_NEEDS_LOCK(instance),             \
00408                                         ::libcwd::_private_::instance >,                        \
00409                           auto_internal_pool                                                    \
00410                           LIBCWD_DEBUGDEBUG_COMMA(::libcwd::_private_::instance)>
00411 
00412 #if LIBCWD_THREAD_SAFE
00413 // Our allocator adaptor for the Non-Shared internal cases: Single Threaded
00414 // (inst = single_threaded_internal_instance) or inside the critical area of the corresponding
00415 // libcwd mutex instance.
00416 #define LIBCWD_NS_INTERNAL_ALLOCATOR(instance)  LIBCWD_CHARALLOCATOR_INTERNAL(instance)
00417 #else // !LIBCWD_THREAD_SAFE
00418 // In a single threaded application, the Non-Shared case is equivalent to the Single Threaded case.
00419 #define LIBCWD_NS_INTERNAL_ALLOCATOR(instance)  LIBCWD_CHARALLOCATOR_INTERNAL(single_threaded_internal_instance)
00420 #endif // !LIBCWD_THREAD_SAFE
00421 
00422 #if LIBCWD_THREAD_SAFE
00423 // LIBCWD_MT_*_ALLOCATOR uses a different allocator than the normal default allocator of libstdc++
00424 // in the case of multi-threading because it can be that the allocator mutex is locked, which would
00425 // result in a deadlock if we try to use it again here.
00426 #define LIBCWD_MT_USERSPACE_ALLOCATOR           LIBCWD_CHARALLOCATOR_USERSPACE(userspace_instance)
00427 #define LIBCWD_MT_INTERNAL_ALLOCATOR            LIBCWD_CHARALLOCATOR_INTERNAL(multi_threaded_internal_instance)
00428 #define LIBCWD_MT_AUTO_INTERNAL_ALLOCATOR       LIBCWD_CHARALLOCATOR_AUTO_INTERNAL(multi_threaded_internal_instance)
00429 #else // !LIBCWD_THREAD_SAFE
00430 // LIBCWD_MT_*_ALLOCATOR uses the normal default allocator of libstdc++-v3 (alloc) using locking
00431 // itself.  The userspace allocator shares it memory pool with everything else (that uses this
00432 // allocator, which is most of the (userspace) STL).
00433 #define LIBCWD_MT_USERSPACE_ALLOCATOR           std::allocator<char>
00434 #define LIBCWD_MT_INTERNAL_ALLOCATOR            LIBCWD_CHARALLOCATOR_INTERNAL(single_threaded_internal_instance)
00435 #define LIBCWD_MT_AUTO_INTERNAL_ALLOCATOR       LIBCWD_CHARALLOCATOR_AUTO_INTERNAL(single_threaded_internal_instance)
00436 #endif // !LIBCWD_THREAD_SAFE
00437 
00438 //---------------------------------------------------------------------------------------------------
00439 // Internal allocator types.
00440 
00441 // This allocator is used in critical areas that are already locked by memblk_map_instance.
00442 typedef LIBCWD_NS_INTERNAL_ALLOCATOR(memblk_map_instance) memblk_map_allocator;
00443 
00444 // This allocator is used in critical areas that are already locked by object_files_instance.
00445 typedef LIBCWD_NS_INTERNAL_ALLOCATOR(object_files_instance) object_files_allocator;
00446 
00447 // This general allocator can be used outside libcwd-specific critical areas,
00448 // but inside a set_alloc_checking_off() .. set_alloc_checking_on() pair.
00449 typedef LIBCWD_MT_INTERNAL_ALLOCATOR internal_allocator;
00450 
00451 // This general allocator can be used outside libcwd-specific critical areas,
00452 // in "user space" but that will cause internal memory to be allocated.
00453 typedef LIBCWD_MT_AUTO_INTERNAL_ALLOCATOR auto_internal_allocator;
00454 
00455 //---------------------------------------------------------------------------------------------------
00456 // User space allocator type.
00457 
00458 // This general allocator can be used outside libcwd-specific critical areas.
00459 typedef LIBCWD_MT_USERSPACE_ALLOCATOR userspace_allocator;
00460 
00461   } // namespace _private_
00462 } // namespace libcwd
00463  
00464 #endif // CWDEBUG_ALLOC
00465 #endif // LIBCWD_PRIVATE_ALLOCATOR_H
00466 
Copyright © 2001 - 2004 Carlo Wood.  All rights reserved.