Fawkes API
Fawkes Development Version
|
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