Fawkes API Fawkes Development Version

memory_manager.cpp

00001 
00002 /***************************************************************************
00003  *  memory_manager.cpp - BlackBoard memory manager
00004  *
00005  *  Created: Sat Sep 23 16:03:40 2006 (INSITE 2006, Joburg, South Africa)
00006  *  Copyright  2006-2008  Tim Niemueller [www.niemueller.de]
00007  *
00008  ****************************************************************************/
00009 
00010 /*  This program is free software; you can redistribute it and/or modify
00011  *  it under the terms of the GNU General Public License as published by
00012  *  the Free Software Foundation; either version 2 of the License, or
00013  *  (at your option) any later version. A runtime exception applies to
00014  *  this software (see LICENSE.GPL_WRE file mentioned below for details).
00015  *
00016  *  This program is distributed in the hope that it will be useful,
00017  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00019  *  GNU Library General Public License for more details.
00020  *
00021  *  Read the full text in the LICENSE.GPL_WRE file in the doc directory.
00022  */
00023 
00024 #include <blackboard/internal/memory_manager.h>
00025 #include <blackboard/exceptions.h>
00026 #include <blackboard/shmem/header.h>
00027 
00028 #include <core/exception.h>
00029 #include <core/exceptions/software.h>
00030 #include <core/exceptions/system.h>
00031 #include <core/threading/mutex.h>
00032 
00033 #include <utils/ipc/shm.h>
00034 #include <utils/ipc/shm_exceptions.h>
00035 
00036 #include <cstdlib>
00037 #include <cstring>
00038 #include <cstdio>
00039 #include <sys/mman.h>
00040 
00041 /** If a free chunk is allocated it may be split up into an allocated
00042  * and a new free chunk. This value determines when this is done. If
00043  * there are at least this many data bytes (without the list header)
00044  * then the chunk is split, otherwise it is fully allocated with
00045  * overhanging bytes.
00046  */
00047 #define BBMM_MIN_FREE_CHUNK_SIZE sizeof(chunk_list_t)
00048 
00049 // shortcuts
00050 #define chunk_ptr(a)  (__shmem ? (chunk_list_t *)__shmem->ptr(a)  : a)
00051 #define chunk_addr(a) (__shmem ? (chunk_list_t *)__shmem->addr(a) : a)
00052 
00053 namespace fawkes {
00054 #if 0 /* just to make Emacs auto-indent happy */
00055 }
00056 #endif
00057 
00058 /** @class BlackBoardMemoryManager <blackboard/internal/memory_manager.h>
00059  * BlackBoard memory manager.
00060  * This class is used by the BlackBoard to manage the memory in the shared memory
00061  * segment. A simple strategy is used for memory management as the expected use case
00062  * is rather simple as well.
00063  *
00064  * The memory is allocated as one big chunk of contiguous memory. Inside this
00065  * chunk the memory manager handles the smaller chunks that are allocated in this
00066  * region. The chunk is allocated as shared memory segment to allow for multi-process
00067  * usage of the memory.
00068  *
00069  * The memory is organized in two separate lists. The one is the free chunks list
00070  * and the other one the allocated chunks list. After startup the allocated
00071  * chunks list is empty while the free chunks list contains one and only one
00072  * big chunk of free memory that contains the whole data segment.
00073  *
00074  * When memory is allocated the smallest chunk that is big enough for the requested
00075  * chunk is used. It is then removed from the free list. If the chunk is big enough
00076  * to hold another chunk of memory (the remaining size can accomodate the header
00077  * and at least as many bytes as the header is in size) the chunk is split into an
00078  * exactly fitting allocated chunk and a remaining free chunk. The chunks are then
00079  * added to the appropriate lists. If there is more memory then requested but
00080  * not enough memory to make it a new free chunk the allocated chunk is enlarged
00081  * to fill the whole chunk. The additional bytes are recorded as overhanging bytes.
00082  *
00083  * When memory is freed the chunk is removed from the allocated chunks list and
00084  * added to the free chunks list. Then the list is cleaned up and adjacent regions
00085  * of free memory are merged to one. Afterwards the free chunks list will contain
00086  * non-ajdacent free memory regions of maximum size between allocated chunks.
00087  *
00088  * The memory manager is thread-safe as all appropriate operations are protected
00089  * by a mutex.
00090  *
00091  * The memory manager has also been prepared for multi-process usage of the
00092  * shared memory region.   but up to now only one process may use the shared
00093  * memory segment.
00094  *
00095  * @todo implement multi-process feature
00096  *
00097  * @author Tim Niemueller
00098  * @see SharedMemory
00099  * @see Mutex
00100  */
00101 
00102 
00103 /** Heap Memory Constructor.
00104  * Constructs a memory segment on the heap.
00105  * @param memsize memory size
00106  */
00107 BlackBoardMemoryManager::BlackBoardMemoryManager(size_t memsize)
00108 {
00109   __shmem        = NULL;
00110   __shmem_header = NULL;
00111   __memsize      = memsize;
00112   __memory       = malloc(memsize);
00113   __mutex        = new Mutex();
00114   __master       = true;
00115 
00116   // Lock memory to RAM to avoid swapping
00117   mlock(__memory, __memsize);
00118 
00119   chunk_list_t *f = (chunk_list_t *)__memory;
00120   f->ptr  = (char *)f + sizeof(chunk_list_t);
00121   f->size = __memsize - sizeof(chunk_list_t);
00122   f->overhang = 0;
00123   f->next = NULL;
00124 
00125   __free_list_head  = f;
00126   __alloc_list_head = NULL;
00127 }
00128 
00129 
00130 /** Shared Memory Constructor
00131  * @param memsize the size of the shared memory segment (data without header)
00132  * that is being managed.
00133  * @param version version of the BlackBoard
00134  * @param master master mode, this memory manager has to be owner of shared memory segment
00135  * @param shmem_token shared memory token, passed to SharedMemory
00136  * @exception BBMemMgrNotMasterException A matching shared memory segment
00137  * has already been created.
00138  * @see SharedMemory::SharedMemory()
00139  */
00140 BlackBoardMemoryManager::BlackBoardMemoryManager(size_t memsize,
00141                                                  unsigned int version,
00142                                                  bool master,
00143                                                  const char *shmem_token)
00144 {
00145   __memory    = NULL;
00146   __memsize   = memsize;
00147   __master    = master;
00148 
00149   // open shared memory segment, if it exists try to aquire exclusive
00150   // semaphore, if that fails, throw an exception
00151 
00152   __shmem_header = new BlackBoardSharedMemoryHeader(__memsize, version);
00153   try {
00154     __shmem = new SharedMemory(shmem_token, __shmem_header,
00155                              /* read only   */ false,
00156                              /* create      */ __master,
00157                              /* dest on del */ __master);
00158     __shmem_header->set_shared_memory(__shmem);
00159   } catch ( ShmCouldNotAttachException &e ) {
00160     delete __shmem_header;
00161     throw BBMemMgrCannotOpenException();
00162   }
00163 
00164   if ( ! __shmem->is_valid() ) {
00165     __shmem->set_destroy_on_delete(false);
00166     delete __shmem;
00167     delete __shmem_header;
00168     throw BBMemMgrCannotOpenException();
00169   }
00170 
00171   if ( master && ! __shmem->is_creator() ) {
00172     // this might mean trouble, we throw an exception if we are not master but
00173     // this was requested
00174     __shmem->set_destroy_on_delete(false);
00175     delete __shmem;
00176     delete __shmem_header;
00177     throw BBNotMasterException("Not owner of shared memory segment");
00178   }
00179 
00180   // printf("Shared memory base pointer: 0x%x\n", (size_t)shmem->getMemPtr());
00181 
00182   if (master) {
00183     // protect memory, needed for list operations in memory, otherwise
00184     // we will have havoc and insanity
00185     __shmem->add_semaphore();
00186 
00187     // This should not be swapped. Will only worked with greatly extended
00188     // ressource limit for this process!
00189     __shmem->set_swapable(false);
00190 
00191     chunk_list_t *f = (chunk_list_t *)__shmem->memptr();
00192     f->ptr  = __shmem->addr((char *)f + sizeof(chunk_list_t));
00193     f->size = __memsize - sizeof(chunk_list_t);
00194     f->overhang = 0;
00195     f->next = NULL;
00196 
00197     __shmem_header->set_free_list_head(f);
00198     __shmem_header->set_alloc_list_head(NULL);
00199   }
00200 
00201   __mutex = new Mutex();
00202 }
00203 
00204 
00205 /** Destructor */
00206 BlackBoardMemoryManager::~BlackBoardMemoryManager()
00207 {
00208   // close shared memory segment, kill semaphore
00209   delete __shmem;
00210   delete __shmem_header;
00211   if (__memory) {
00212     ::free(__memory);
00213   }
00214   delete __mutex;
00215 }
00216 
00217 
00218 /** Allocate memory.
00219  * This will allocate memory in the shared memory segment. The strategy is described
00220  * in the class description. Note: this method does NOT lock the shared memory
00221  * system. Chaos and havoc will come down upon you if you do not ensure locking!
00222  * @exception OutOfMemoryException thrown if not enough free memory is available to
00223  *                                 accommodate a chunk of the desired size
00224  * @param num_bytes number of bytes to allocate
00225  * @return pointer to the memory chunk
00226  */
00227 void *
00228 BlackBoardMemoryManager::alloc_nolock(unsigned int num_bytes)
00229 {
00230   // search for smallest chunk just big enough for desired size
00231   chunk_list_t *l = __shmem ? __shmem_header->free_list_head() : __free_list_head;
00232 
00233   // Note: free chunks list sorted ascending by ptr
00234   chunk_list_t *f = NULL;
00235   while ( l ) {
00236     if ( (l->size >= num_bytes) && // chunk is big enough
00237          ( (f == NULL) || (l->size < f->size) ) ) { // no chunk found or current chunk smaller
00238       f = l;
00239     }
00240     l = chunk_ptr(l->next);
00241   }
00242 
00243   if ( f == NULL ) {
00244     // Doh, did not find chunk
00245     throw OutOfMemoryException("BlackBoard ran out of memory");
00246   }
00247 
00248   // remove chunk from free_list
00249   if ( __shmem ) {
00250     __shmem_header->set_free_list_head( list_remove(__shmem_header->free_list_head(), f) );
00251   } else {
00252     __free_list_head = list_remove(__free_list_head, f);
00253   }
00254 
00255   /*
00256   // only chunk's semaphore
00257   if ( ptr_sems.find( f->ptr ) != ptr_sems.end() ) {
00258     SemaphoreSet *s = ptr_sems[f->ptr];
00259     delete s;
00260     ptr_sems.erase( f->ptr );
00261     f->semset_key = 0;
00262   }
00263   */
00264 
00265   // our old free list chunk is now our new alloc list chunk
00266   // check if there is free space beyond the requested size that makes it worth
00267   // entering it into the free list
00268   if ( f->size >= (num_bytes + BBMM_MIN_FREE_CHUNK_SIZE + sizeof(chunk_list_t)) ) {
00269     // we will have a new free chunk afterwards
00270     chunk_list_t *nfc = (chunk_list_t *)((char *)f + sizeof(chunk_list_t) + num_bytes);
00271     nfc->ptr = __shmem ? __shmem->addr((char *)nfc + sizeof(chunk_list_t)) : (char *)nfc + sizeof(chunk_list_t);
00272     nfc->size = f->size - num_bytes - sizeof(chunk_list_t);
00273     nfc->overhang = 0;
00274     
00275     if ( __shmem ) {
00276       __shmem_header->set_free_list_head( list_add(__shmem_header->free_list_head(), nfc) );
00277     } else {
00278       __free_list_head = list_add(__free_list_head, nfc);
00279     }
00280 
00281     f->size = num_bytes;
00282   } else {
00283     // chunk is too small for another free chunk, now we have allocated but unusued
00284     // space, this is ok but not desireable
00285     // this is only informational!
00286     f->overhang = f->size - num_bytes;
00287   }
00288 
00289   // alloc new chunk
00290   if ( __shmem ) {
00291     __shmem_header->set_alloc_list_head( list_add(__shmem_header->alloc_list_head(), f) );
00292     return __shmem->ptr(f->ptr);
00293   } else {
00294     __alloc_list_head = list_add(__alloc_list_head, f);
00295     return f->ptr;
00296   }
00297 
00298 }
00299 
00300 
00301 /** Allocate memory.
00302  * This will allocate memory in the shared memory segment. The strategy is described
00303  * in the class description.
00304  * @exception OutOfMemoryException thrown if not enough free memory is available to
00305  *                                 accommodate a chunk of the desired size
00306  * @param num_bytes number of bytes to allocate
00307  * @return pointer to the memory chunk
00308  */
00309 void *
00310 BlackBoardMemoryManager::alloc(unsigned int num_bytes)
00311 {
00312   void * ptr;
00313   __mutex->lock();
00314   if (__shmem) __shmem->lock_for_write();
00315   try {
00316     ptr = alloc_nolock(num_bytes);
00317   } catch (Exception &e) {
00318     if (__shmem) __shmem->unlock();
00319     __mutex->unlock();
00320     throw;
00321   }
00322   if (__shmem) __shmem->unlock();
00323   __mutex->unlock();
00324   return ptr;
00325 }
00326 
00327 
00328 /** Free a memory chunk.
00329  * Frees a previously allocated chunk. Not that you have to give the exact pointer
00330  * that was returned by alloc(). You may not give a pointer inside a memory chunk or
00331  * even worse outside of it! See the class description for a brief description of
00332  * the strategy used.
00333  * @param ptr pointer to the chunk of memory
00334  * @exception BlackBoardMemMgrInvalidPointerException a pointer that has not been
00335  * previously returned by alloc() has been given and could not be found in the
00336  * allocated chunks list.
00337  */
00338 void
00339 BlackBoardMemoryManager::free(void *ptr)
00340 {
00341   __mutex->lock();
00342   if (__shmem) {
00343     __shmem->lock_for_write();
00344 
00345     // find chunk in alloc_chunks
00346     chunk_list_t *ac = list_find_ptr(__shmem_header->alloc_list_head(), chunk_addr(ptr));
00347     if ( ac == NULL ) {
00348       throw BlackBoardMemMgrInvalidPointerException();
00349     }
00350 
00351     // remove from alloc_chunks
00352     __shmem_header->set_alloc_list_head( list_remove(__shmem_header->alloc_list_head(), ac) );
00353 
00354     // reclaim as free memory
00355     ac->overhang = 0;
00356     __shmem_header->set_free_list_head( list_add(__shmem_header->free_list_head(), ac) );
00357 
00358     // merge adjacent regions
00359     cleanup_free_chunks();
00360 
00361     __shmem->unlock();
00362   } else {
00363     // find chunk in alloc_chunks
00364     chunk_list_t *ac = list_find_ptr(__alloc_list_head, ptr);
00365     if ( ac == NULL ) {
00366       throw BlackBoardMemMgrInvalidPointerException();
00367     }
00368 
00369     // remove from alloc_chunks
00370     __alloc_list_head =  list_remove(__alloc_list_head, ac);
00371 
00372     // reclaim as free memory
00373     ac->overhang = 0;
00374     __free_list_head = list_add(__free_list_head, ac);
00375 
00376     // merge adjacent regions
00377     cleanup_free_chunks();
00378   }
00379 
00380   __mutex->unlock();
00381 }
00382 
00383 
00384 /** Check memory consistency.
00385  * This method checks the consistency of the memory segment. It controls whether
00386  * all the memory is covered by the free and allocated chunks lists and if there is
00387  * no unmanaged memory between chunks.
00388  * @exception BBInconsistentMemoryException thrown if the memory segment has been
00389  * corrupted. Contains descriptive message.
00390  */
00391 void
00392 BlackBoardMemoryManager::check()
00393 {
00394   chunk_list_t *f = __shmem ? __shmem_header->free_list_head() : __free_list_head;
00395   chunk_list_t *a = __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head;
00396   chunk_list_t *t = NULL;
00397 
00398   unsigned int mem = 0;
00399 
00400   // we crawl through the memory and analyse if the chunks are continuous,
00401   // assumption: chunk list sorted ascending by ptr
00402   while ( f || a ) {
00403     if ( f == NULL ) {
00404       mem += a->size + sizeof(chunk_list_t);
00405       t = chunk_ptr(a->next);
00406       if ( t ) {
00407         // check if a is continuous
00408         void *next = (char *)a->ptr + a->size + sizeof(chunk_list_t);
00409         if ( next != t->ptr ) {
00410           throw BBInconsistentMemoryException("non-contiguos allocated memory");        
00411         }
00412       }
00413       a = t;
00414     } else if ( a == NULL ) {
00415       mem += f->size + sizeof(chunk_list_t);
00416       t = chunk_ptr(f->next);
00417       if ( t ) {
00418         // check if f is continuous
00419         void *next = (char *)f->ptr + f->size + sizeof(chunk_list_t);
00420         if ( next != t->ptr ) {
00421           throw BBInconsistentMemoryException("non-contiguos allocated memory");        
00422         }
00423       }
00424       f = t;
00425     } else if ( f->ptr == a->ptr ) {
00426       throw BBInconsistentMemoryException("ptr cannot be free and allocated at the same time");
00427     } else if ( f->ptr < a->ptr ) {
00428       mem += f->size + sizeof(chunk_list_t);
00429       void *next = (char *)f->ptr + f->size;
00430       t = chunk_ptr(f->next);
00431       if ( (next != t) && (next != a) ) {
00432         throw BBInconsistentMemoryException("there are unallocated bytes between chunks (f)");
00433       }
00434       f = t;
00435     } else {
00436       mem += a->size + sizeof(chunk_list_t);
00437       void *next = (char *)a->ptr + a->size;
00438       t = chunk_ptr(a->next);
00439       if ( (next != t) && (next != f) ) {
00440         throw BBInconsistentMemoryException("there are unallocated bytes between chunks (a)");
00441       }
00442       a = t;
00443     }
00444   }
00445 
00446   if ( mem != __memsize ) {
00447     throw BBInconsistentMemoryException("unmanaged memory found, managed memory size != total memory size");
00448   }
00449 }
00450 
00451 
00452 /** Check if this BB memory manager is the master.
00453  * @return true if this BB memory manager instance is the master for the BB
00454  * shared memory segment, false otherwise
00455  */
00456 bool
00457 BlackBoardMemoryManager::is_master() const
00458 {
00459   return __master;
00460 }
00461 
00462 
00463 /** Print out info about free chunks.
00464  * Prints out a formatted list of free chunks.
00465  */
00466 void
00467 BlackBoardMemoryManager::print_free_chunks_info() const
00468 {
00469   list_print_info( __shmem ? __shmem_header->free_list_head() : __free_list_head );
00470 }
00471 
00472 
00473 /** Print out info about allocated chunks.
00474  * Prints out a formatted list of allocated chunks.
00475  */
00476 void
00477 BlackBoardMemoryManager::print_allocated_chunks_info() const
00478 {
00479   list_print_info( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head );
00480 }
00481 
00482 
00483 /** Prints out performance info.
00484  * This will print out information about the number of free and allocated chunks,
00485  * the maximum free and allocated chunk size and the number of overhanging bytes
00486  * (see class description about overhanging bytes).
00487  */
00488 void
00489 BlackBoardMemoryManager::print_performance_info() const
00490 {
00491   printf("free chunks: %6u, alloc chunks: %6u, max free: %10u, max alloc: %10u, overhang: %10u\n",
00492          list_length( __shmem ? __shmem_header->free_list_head() : __free_list_head),
00493          list_length( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head),
00494          max_free_size(), max_allocated_size(), overhang_size());
00495 }
00496 
00497 
00498 /** Get maximum allocatable memory size.
00499  * This method gives information about the maximum free chunk size and thus
00500  * the maximum of memory that can be allocated in one chunk.
00501  * @return maximum free chunk size
00502  */
00503 unsigned int
00504 BlackBoardMemoryManager::max_free_size() const
00505 {
00506   chunk_list_t *m = list_get_biggest( __shmem ? __shmem_header->free_list_head() : __free_list_head );
00507   if ( m == NULL ) {
00508     return 0;
00509   } else {
00510     return m->size;
00511   }
00512 }
00513 
00514 
00515 /** Get total free memory.
00516  * This method gives information about the sum of all free chunk sizes. Note that
00517  * it is not guaranteed that that much data can be stored in the memory since
00518  * fragmentation may have occured. To get information about the biggest piece
00519  * of memory that you can allocate use getMaxFreeSize()
00520  * @return sum of free chunk sizes
00521  */
00522 unsigned int
00523 BlackBoardMemoryManager::free_size() const
00524 {
00525   unsigned int free_size = 0;
00526   chunk_list_t *l = __shmem ? __shmem_header->free_list_head() : __free_list_head;
00527   while ( l ) {
00528     free_size += l->size;
00529     l = chunk_ptr(l->next);
00530   }
00531   return free_size;
00532 }
00533 
00534 
00535 /** Get total allocated memory.
00536  * This method gives information about the sum of all allocated chunk sizes.
00537  * @return sum of allocated chunks sizes
00538  */
00539 unsigned int
00540 BlackBoardMemoryManager::allocated_size() const
00541 {
00542   unsigned int alloc_size = 0;
00543   chunk_list_t *l = __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head;
00544   while ( l ) {
00545     alloc_size += l->size;
00546     l = chunk_ptr(l->next);
00547   }
00548   return alloc_size;
00549 }
00550 
00551 
00552 /** Get number of allocated chunks.
00553  * @return number of allocated memory chunks
00554  */
00555 unsigned int
00556 BlackBoardMemoryManager::num_allocated_chunks() const
00557 {
00558   return list_length( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head );
00559 }
00560 
00561 
00562 /** Get number of free chunks.
00563  * @return number of free memory chunks
00564  */
00565 unsigned int
00566 BlackBoardMemoryManager::num_free_chunks() const
00567 {
00568   return list_length( __shmem ? __shmem_header->free_list_head() : __free_list_head );
00569 }
00570 
00571 
00572 /** Get size of memory.
00573  * This does not include memory headers, but only the size of the data segment.
00574  * @return size of memory.
00575  */
00576 unsigned int
00577 BlackBoardMemoryManager::memory_size() const
00578 {
00579   return __memsize;
00580 }
00581 
00582 
00583 /** Get BlackBoard version.
00584  * @return BlackBoard version
00585  */
00586 unsigned int
00587 BlackBoardMemoryManager::version() const
00588 {
00589   return __shmem ? __shmem_header->version() : 0;
00590 }
00591 
00592 
00593 /** Lock memory.
00594  * Locks the whole memory segment used and managed by the memory manager. Will
00595  * aquire local mutex lock and global semaphore lock in shared memory segment.
00596  */
00597 void
00598 BlackBoardMemoryManager::lock()
00599 {
00600   __mutex->lock();
00601   if (__shmem) __shmem->lock_for_write();
00602 }
00603 
00604 
00605 /** Try to lock memory.
00606  * Tries to lock the whole memory segment used and managed by the memory manager. Will
00607  * aquire local mutex lock and global semaphore lock in shared memory segment.
00608  * The lock has been successfully aquired if both of these locks could be aquired!
00609  * @return true, if the lock could be aquired, false otherwise.
00610  */
00611 bool
00612 BlackBoardMemoryManager::try_lock()
00613 {
00614   if ( __mutex->try_lock() ) {
00615     if (__shmem) {
00616       if ( __shmem->try_lock_for_write() ) {
00617         return true;
00618       } else {
00619         __mutex->unlock();
00620       }
00621     } else {
00622       return true;
00623     }
00624   }
00625 
00626   return false;
00627 }
00628 
00629 
00630 /** Unlock memory.
00631  * Releases the lock hold on the shared memory segment and the local mutex lock.
00632  */
00633 void
00634 BlackBoardMemoryManager::unlock()
00635 {
00636   if (__shmem) __shmem->unlock();
00637   __mutex->unlock();
00638 }
00639 
00640 
00641 /** Get maximum alloced memory size.
00642  * This method gives information about the maximum allocated chunk size and thus
00643  * the maximum of memory that has been be allocated in one chunk.
00644  * @return maximum allocated chunk size
00645  */
00646 unsigned int
00647 BlackBoardMemoryManager::max_allocated_size() const
00648 {
00649   chunk_list_t *m = list_get_biggest( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head);
00650   if ( m == NULL ) {
00651     return 0;
00652   } else {
00653     return m->size;
00654   }
00655 }
00656 
00657 
00658 /** Get number of overhanging bytes.
00659  * The number of overhanging bytes. See class description for more info about
00660  * overhanging bytes.
00661  * @return number of overhanging bytes
00662  */
00663 unsigned int
00664 BlackBoardMemoryManager::overhang_size() const
00665 {
00666   unsigned int overhang = 0;
00667   chunk_list_t *a = __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head;
00668   while ( a ) {
00669     overhang += a->overhang;
00670     a = chunk_ptr(a->next);
00671   }
00672   return overhang;
00673 }
00674 
00675 
00676 /** Cleanup and merge free chunks.
00677  * This will merge adjacent free chunks into one big chunk. After this method ran it
00678  * is guaranteed that the maximum available memory resides in one chunk.
00679  */
00680 void
00681 BlackBoardMemoryManager::cleanup_free_chunks()
00682 {
00683   bool modified = true;
00684   chunk_list_t *l;
00685   chunk_list_t *n; // next
00686         
00687   while (modified) {
00688     modified = false;
00689     l = __shmem ? __shmem_header->free_list_head() : __free_list_head;
00690     n = chunk_ptr(l->next);
00691     while ( l && n) {
00692       if ( ((char *)l->ptr + l->size + sizeof(chunk_list_t)) == n->ptr ) {
00693         // re-unite
00694         l->size += n->size + sizeof(chunk_list_t);
00695         l->next = n->next;
00696         modified = true;
00697       }
00698       l = n;
00699       n = chunk_ptr(l->next);
00700     }
00701   }
00702 }
00703 
00704 
00705 /** Remove an element from a list.
00706  * @param list list to remove the element from
00707  * @param rmel element to remove
00708  * @return the head of the new resulting list
00709  * @exception NullPointerException thrown if list or rmel equals NULL
00710  */
00711 chunk_list_t *
00712 BlackBoardMemoryManager::list_remove(chunk_list_t *list, chunk_list_t *rmel)
00713 {
00714   if ( list == NULL )
00715     throw NullPointerException("BlackBoardMemoryManager::list_remove: list == NULL");
00716   if ( rmel == NULL )
00717     throw NullPointerException("BlackBoardMemoryManager::list_remove: rmel == NULL");
00718 
00719 
00720   chunk_list_t *new_head = list;
00721   chunk_list_t *l = list;
00722   chunk_list_t *p = NULL;
00723 
00724   while ( l ) {
00725     if ( l == rmel ) {
00726       // found element, now remove
00727       if ( p ) {
00728         // we have a predecessor
00729         p->next = l->next;
00730       } else {
00731         // new head
00732         new_head = chunk_ptr(l->next);
00733       }
00734       break;
00735     }
00736     p = l;
00737     l = chunk_ptr(l->next);
00738   }
00739 
00740   return new_head;
00741 }
00742 
00743 
00744 /** Add an element to a list.
00745  * @param list list to add the element to
00746  * @param rmel element to add
00747  * @return the head of the new resulting list
00748  * @exception NullPointerException thrown if addel equals NULL
00749  */
00750 chunk_list_t *
00751 BlackBoardMemoryManager::list_add(chunk_list_t *list, chunk_list_t *addel)
00752 {
00753   if ( addel == NULL )
00754     throw NullPointerException("BlackBoardMemoryManager::list_add: addel == NULL");
00755 
00756   chunk_list_t *new_head = list;
00757   chunk_list_t *l = list;
00758   chunk_list_t *p = NULL;
00759 
00760   while ( l ) {
00761     if ( addel->ptr < l->ptr ) {
00762       // add it here
00763       addel->next = chunk_addr(l);
00764       if ( p != NULL ) {
00765         // predecessor needs new successor
00766         // before: p->next == l
00767         p->next = chunk_addr(addel);
00768       } else {
00769         new_head = addel;
00770       }
00771       // used as condition below
00772       l = addel;
00773       break;
00774     } else {
00775       p = l;
00776       l = chunk_ptr(l->next);
00777     }
00778   }
00779 
00780   // if l is not addel it has not yet been added
00781   if ( l != addel ) {
00782     // p is last element of list and != NULL
00783     addel->next = NULL;
00784     if ( p ) {
00785       p->next     = chunk_addr(addel);
00786     } else {
00787       new_head = addel;
00788     }
00789   }
00790 
00791   return new_head;
00792 }
00793 
00794 
00795 /** Find a chunk by ptr.
00796  * @param list list to search
00797  * @param ptr Pointer to search for
00798  * @return the chunk that points to ptr or NULL if not found
00799  */
00800 chunk_list_t *
00801 BlackBoardMemoryManager::list_find_ptr(chunk_list_t *list, void *ptr)
00802 {
00803   chunk_list_t *l = list;
00804   while ( l ) {
00805     if ( l->ptr == ptr ) {
00806       // found it
00807       return l;
00808     } else {
00809       l = chunk_ptr(l->next);
00810     }
00811   }
00812   return NULL;
00813 }
00814 
00815 
00816 /** Print info about chunks in list.
00817  * Will print information about chunks in list to stdout. Will give pointer as hexadezimal
00818  * number, size and overhanging bytes of chunk
00819  * @param list list with chunks to print
00820  */
00821 void
00822 BlackBoardMemoryManager::list_print_info(const chunk_list_t *list) const
00823 {
00824   chunk_list_t *l = (chunk_list_t *)list;
00825   unsigned int i = 0;
00826 
00827   while ( l ) {
00828     printf("Chunk %3u:  0x%x   size=%10u bytes   overhang=%10u bytes\n",
00829            ++i, (unsigned int)(size_t)l->ptr, l->size, l->overhang);
00830     l = chunk_ptr(l->next);
00831   }
00832 
00833 }
00834 
00835 
00836 /** Get length of list.
00837  * @param list list to count
00838  * @return length of list
00839  */
00840 unsigned int
00841 BlackBoardMemoryManager::list_length(const chunk_list_t *list) const
00842 {
00843   unsigned int l = 0;
00844   while ( list ) {
00845     ++l;
00846     list = chunk_ptr(list->next);
00847   }
00848   return l;
00849 }
00850 
00851 
00852 /** Get biggest chunk from list.
00853  * @param list list to search
00854  * @return biggest chunk in list
00855  */
00856 chunk_list_t *
00857 BlackBoardMemoryManager::list_get_biggest(const chunk_list_t *list) const
00858 {
00859   chunk_list_t *b = (chunk_list_t *)list;
00860   chunk_list_t *l = (chunk_list_t *)list;
00861   while ( l ) {
00862     if ( l->size > b->size ) {
00863       b = l;
00864     }
00865     l = chunk_ptr(l->next);
00866   }
00867 
00868   return b;
00869 }
00870 
00871 /** Get first element for chunk iteration.
00872  * @return Iterator pointing to first memory chunk
00873  */
00874 BlackBoardMemoryManager::ChunkIterator
00875 BlackBoardMemoryManager::begin()
00876 {
00877   if (__shmem) {
00878     return BlackBoardMemoryManager::ChunkIterator(__shmem, __shmem_header->alloc_list_head() );
00879   } else {
00880     return BlackBoardMemoryManager::ChunkIterator(__alloc_list_head);
00881   }
00882 }
00883 
00884 /** Get end of chunk list.
00885  * This returns an iterator that points to the element just beyond the allocated
00886  * chunk list.
00887  * @return ChunkIterator pointing to a non-existant element beyond the chunk list
00888  */
00889 BlackBoardMemoryManager::ChunkIterator
00890 BlackBoardMemoryManager::end()
00891 {
00892   return BlackBoardMemoryManager::ChunkIterator();
00893 }
00894 
00895 
00896 /** @class BlackBoardMemoryManager::ChunkIterator <blackboard/internal/memory_manager.h>
00897  * Iterator for memory chunks.
00898  * The ChunkIterator can be used to iterate over all allocated memory chunks
00899  * in the memory segment.
00900  */
00901 
00902 /** Constructor.
00903  * Will create a instance pointing beyond the end of the lits.
00904  */
00905 BlackBoardMemoryManager::ChunkIterator::ChunkIterator()
00906 {
00907   __shmem = NULL;
00908   __cur   = NULL;
00909 }
00910 
00911 /** Constructor
00912  * @param shmem shared memory segkent
00913  * @param cur Current element for chunk list
00914  */
00915 BlackBoardMemoryManager::ChunkIterator::ChunkIterator(SharedMemory *shmem,
00916                                                       chunk_list_t *cur)
00917 {
00918   __shmem = shmem;
00919   __cur   = cur;
00920 }
00921 
00922 
00923 /** Constructor
00924  * @param cur Current element for chunk list
00925  */
00926 BlackBoardMemoryManager::ChunkIterator::ChunkIterator(chunk_list_t *cur)
00927 {
00928   __shmem = NULL;
00929   __cur   = cur;
00930 }
00931 
00932 
00933 /** Copy constructor.
00934  * @param it Iterator to copy
00935  */
00936 BlackBoardMemoryManager::ChunkIterator::ChunkIterator(const ChunkIterator &it)
00937 {
00938   __shmem = it.__shmem;
00939   __cur   = it.__cur;
00940 }
00941 
00942 
00943 /** Increment iterator.
00944  * Advances to the next element. This is the infix-operator. It may be used
00945  * like this:
00946  * @code
00947  * for (ChunkIterator cit = memmgr->begin(); cit != memmgr->end(); ++cit) {
00948  *   // your code here
00949  * }
00950  * @endcode
00951  * @return Reference to instance itself after advancing to the next element.
00952  */
00953 BlackBoardMemoryManager::ChunkIterator &
00954 BlackBoardMemoryManager::ChunkIterator::operator++()
00955 {
00956   if ( __cur != NULL )  __cur = chunk_ptr(__cur->next);
00957 
00958   return *this;
00959 }
00960 
00961 
00962 /** Increment iterator.
00963  * Advances to the next element in allocated chunk list. This is the postfix-operator.
00964  * It may be used like this:
00965  * @code
00966  * for (ChunkIterator cit = memmgr->begin(); cit != memmgr->end(); cit++) {
00967  *   // your code here
00968  * }
00969  * @endcode
00970  * Note that since a copy of the original iterator has to be created an returned it
00971  * the postfix operation takes both, more CPU time and more memory. If possible (especially
00972  * if used in a for loop like the example) use the prefix operator!
00973  * @see operator++()
00974  * @param inc ignored
00975  * @return copy of the current instance before advancing to the next element.
00976  */
00977 BlackBoardMemoryManager::ChunkIterator
00978 BlackBoardMemoryManager::ChunkIterator::operator++(int inc)
00979 {
00980   ChunkIterator rv(*this);
00981   if ( __cur != NULL )  __cur = chunk_ptr(__cur->next);
00982 
00983   return rv;
00984 }
00985 
00986 
00987 /** Advance by a certain amount.
00988  * Can be used to add an integer to the iterator to advance many steps in one go.
00989  * This operation takes linear time depending on i.
00990  * @param i steps to advance in list. If i is bigger than the number of remaining
00991  * elements in the list will stop beyond list.
00992  * @return reference to current instance after advancing i steps or after reaching
00993  * end of list.
00994  */
00995 BlackBoardMemoryManager::ChunkIterator &
00996 BlackBoardMemoryManager::ChunkIterator::operator+(unsigned int i)
00997 {
00998   for (unsigned int j = 0; (__cur != NULL) && (j < i); ++j) {
00999     if ( __cur != NULL )  __cur = chunk_ptr(__cur->next);
01000   }
01001   return *this;
01002 }
01003 
01004 
01005 /** Advance by a certain amount.
01006  * Works like operator+(unsigned int i), provided for convenience.
01007  * @param i steps to advance in list
01008  * @return reference to current instance after advancing i steps or after reaching
01009  * end of list.
01010  */
01011 BlackBoardMemoryManager::ChunkIterator &
01012 BlackBoardMemoryManager::ChunkIterator::operator+=(unsigned int i)
01013 {
01014   for (unsigned int j = 0; (__cur != NULL) && (j < i); ++j) {
01015     if ( __cur != NULL )  __cur = chunk_ptr(__cur->next);
01016   }
01017   return *this;
01018 }
01019 
01020 
01021 /** Check equality of two iterators.
01022  * Can be used to determine if two iterators point to the same chunk.
01023  * @param c iterator to compare current instance to
01024  * @return true, if iterators point to the same chunk, false otherwise
01025  */
01026 bool
01027 BlackBoardMemoryManager::ChunkIterator::operator==(const ChunkIterator & c) const
01028 {
01029   return (__cur == c.__cur);
01030 }
01031 
01032 
01033 /** Check inequality of two iterators.
01034  * Can be used to determine if two iterators point to different chunks.
01035  * @param c iterator to compare current instance to
01036  * @return true, if iterators point to different chunks of memory, false otherwise
01037  */
01038 bool
01039 BlackBoardMemoryManager::ChunkIterator::operator!=(const ChunkIterator & c) const
01040 {
01041   return (__cur != c.__cur);
01042 }
01043 
01044 
01045 /** Get memory pointer of chunk.
01046  * Use this operator to get the pointer to the chunk of memory that this iterator
01047  * points to.
01048  * @return pointer to memory
01049  */
01050 void *
01051 BlackBoardMemoryManager::ChunkIterator::operator*() const
01052 {
01053   if ( __cur == NULL )  return NULL;
01054 
01055   if (__shmem) return __shmem->ptr(__cur->ptr);
01056   else         return __cur->ptr;
01057 }
01058 
01059 
01060 /** Assign iterator.
01061  * Makes the current instance to point to the same memory element as c.
01062  * @param c assign value
01063  * @return reference to current instance
01064  */
01065 BlackBoardMemoryManager::ChunkIterator &
01066 BlackBoardMemoryManager::ChunkIterator::operator=(const ChunkIterator & c)
01067 {
01068   __shmem = c.__shmem;
01069   __cur   = c.__cur;
01070   return *this;
01071 }
01072 
01073 
01074 /** Get size of data segment.
01075  * Returns the size of the memory chunk. This includes overhanging bytes.
01076  * @return size of chunk including overhanging bytes
01077  */
01078 unsigned int
01079 BlackBoardMemoryManager::ChunkIterator::size() const
01080 {
01081   return ( __cur != NULL ) ? __cur->size : 0;
01082 }
01083 
01084 
01085 /** Get number of overhanging bytes.
01086  * See documentation of BlackBoardMemoryManager about overhanging bytes.
01087  * @see BlackBoardMemoryManager
01088  * @return number of overhanging bytes.
01089  */
01090 unsigned int
01091 BlackBoardMemoryManager::ChunkIterator::overhang() const
01092 {
01093   return ( __cur != NULL ) ? __cur->overhang : 0;
01094 }
01095 
01096 } // end namespace fawkes
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends