Fawkes API  Fawkes Development Version
 All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends Groups Pages
memory_manager.cpp
1 
2 /***************************************************************************
3  * memory_manager.cpp - BlackBoard memory manager
4  *
5  * Created: Sat Sep 23 16:03:40 2006 (INSITE 2006, Joburg, South Africa)
6  * Copyright 2006-2008 Tim Niemueller [www.niemueller.de]
7  *
8  ****************************************************************************/
9 
10 /* This program is free software; you can redistribute it and/or modify
11  * it under the terms of the GNU General Public License as published by
12  * the Free Software Foundation; either version 2 of the License, or
13  * (at your option) any later version. A runtime exception applies to
14  * this software (see LICENSE.GPL_WRE file mentioned below for details).
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19  * GNU Library General Public License for more details.
20  *
21  * Read the full text in the LICENSE.GPL_WRE file in the doc directory.
22  */
23 
24 #include <blackboard/internal/memory_manager.h>
25 #include <blackboard/exceptions.h>
26 #include <blackboard/shmem/header.h>
27 
28 #include <core/exception.h>
29 #include <core/exceptions/software.h>
30 #include <core/exceptions/system.h>
31 #include <core/threading/mutex.h>
32 
33 #include <utils/ipc/shm.h>
34 #include <utils/ipc/shm_exceptions.h>
35 
36 #include <cstdlib>
37 #include <cstring>
38 #include <cstdio>
39 #include <sys/mman.h>
40 
41 /** If a free chunk is allocated it may be split up into an allocated
42  * and a new free chunk. This value determines when this is done. If
43  * there are at least this many data bytes (without the list header)
44  * then the chunk is split, otherwise it is fully allocated with
45  * overhanging bytes.
46  */
47 #define BBMM_MIN_FREE_CHUNK_SIZE sizeof(chunk_list_t)
48 
49 // shortcuts
50 #define chunk_ptr(a) (__shmem ? (chunk_list_t *)__shmem->ptr(a) : a)
51 #define chunk_addr(a) (__shmem ? (chunk_list_t *)__shmem->addr(a) : a)
52 
53 namespace fawkes {
54 #if 0 /* just to make Emacs auto-indent happy */
55 }
56 #endif
57 
58 /** @class BlackBoardMemoryManager <blackboard/internal/memory_manager.h>
59  * BlackBoard memory manager.
60  * This class is used by the BlackBoard to manage the memory in the shared memory
61  * segment. A simple strategy is used for memory management as the expected use case
62  * is rather simple as well.
63  *
64  * The memory is allocated as one big chunk of contiguous memory. Inside this
65  * chunk the memory manager handles the smaller chunks that are allocated in this
66  * region. The chunk is allocated as shared memory segment to allow for multi-process
67  * usage of the memory.
68  *
69  * The memory is organized in two separate lists. The one is the free chunks list
70  * and the other one the allocated chunks list. After startup the allocated
71  * chunks list is empty while the free chunks list contains one and only one
72  * big chunk of free memory that contains the whole data segment.
73  *
74  * When memory is allocated the smallest chunk that is big enough for the requested
75  * chunk is used. It is then removed from the free list. If the chunk is big enough
76  * to hold another chunk of memory (the remaining size can accomodate the header
77  * and at least as many bytes as the header is in size) the chunk is split into an
78  * exactly fitting allocated chunk and a remaining free chunk. The chunks are then
79  * added to the appropriate lists. If there is more memory then requested but
80  * not enough memory to make it a new free chunk the allocated chunk is enlarged
81  * to fill the whole chunk. The additional bytes are recorded as overhanging bytes.
82  *
83  * When memory is freed the chunk is removed from the allocated chunks list and
84  * added to the free chunks list. Then the list is cleaned up and adjacent regions
85  * of free memory are merged to one. Afterwards the free chunks list will contain
86  * non-ajdacent free memory regions of maximum size between allocated chunks.
87  *
88  * The memory manager is thread-safe as all appropriate operations are protected
89  * by a mutex.
90  *
91  * The memory manager has also been prepared for multi-process usage of the
92  * shared memory region. but up to now only one process may use the shared
93  * memory segment.
94  *
95  * @todo implement multi-process feature
96  *
97  * @author Tim Niemueller
98  * @see SharedMemory
99  * @see Mutex
100  */
101 
102 
103 /** Heap Memory Constructor.
104  * Constructs a memory segment on the heap.
105  * @param memsize memory size
106  */
107 BlackBoardMemoryManager::BlackBoardMemoryManager(size_t memsize)
108 {
109  __shmem = NULL;
110  __shmem_header = NULL;
111  __memsize = memsize;
112  __memory = malloc(memsize);
113  __mutex = new Mutex();
114  __master = true;
115 
116  // Lock memory to RAM to avoid swapping
117  mlock(__memory, __memsize);
118 
119  chunk_list_t *f = (chunk_list_t *)__memory;
120  f->ptr = (char *)f + sizeof(chunk_list_t);
121  f->size = __memsize - sizeof(chunk_list_t);
122  f->overhang = 0;
123  f->next = NULL;
124 
125  __free_list_head = f;
126  __alloc_list_head = NULL;
127 }
128 
129 
130 /** Shared Memory Constructor
131  * @param memsize the size of the shared memory segment (data without header)
132  * that is being managed.
133  * @param version version of the BlackBoard
134  * @param master master mode, this memory manager has to be owner of shared memory segment
135  * @param shmem_token shared memory token, passed to SharedMemory
136  * @exception BBMemMgrNotMasterException A matching shared memory segment
137  * has already been created.
138  * @see SharedMemory::SharedMemory()
139  */
140 BlackBoardMemoryManager::BlackBoardMemoryManager(size_t memsize,
141  unsigned int version,
142  bool master,
143  const char *shmem_token)
144 {
145  __memory = NULL;
146  __memsize = memsize;
147  __master = master;
148 
149  // open shared memory segment, if it exists try to aquire exclusive
150  // semaphore, if that fails, throw an exception
151 
152  __shmem_header = new BlackBoardSharedMemoryHeader(__memsize, version);
153  try {
154  __shmem = new SharedMemory(shmem_token, __shmem_header,
155  /* read only */ false,
156  /* create */ __master,
157  /* dest on del */ __master);
158  __shmem_header->set_shared_memory(__shmem);
159  } catch ( ShmCouldNotAttachException &e ) {
160  delete __shmem_header;
162  }
163 
164  if ( ! __shmem->is_valid() ) {
165  __shmem->set_destroy_on_delete(false);
166  delete __shmem;
167  delete __shmem_header;
169  }
170 
171  if ( master && ! __shmem->is_creator() ) {
172  // this might mean trouble, we throw an exception if we are not master but
173  // this was requested
174  __shmem->set_destroy_on_delete(false);
175  delete __shmem;
176  delete __shmem_header;
177  throw BBNotMasterException("Not owner of shared memory segment");
178  }
179 
180  // printf("Shared memory base pointer: 0x%x\n", (size_t)shmem->getMemPtr());
181 
182  if (master) {
183  // protect memory, needed for list operations in memory, otherwise
184  // we will have havoc and insanity
185  __shmem->add_semaphore();
186 
187  // This should not be swapped. Will only worked with greatly extended
188  // ressource limit for this process!
189  __shmem->set_swapable(false);
190 
191  chunk_list_t *f = (chunk_list_t *)__shmem->memptr();
192  f->ptr = __shmem->addr((char *)f + sizeof(chunk_list_t));
193  f->size = __memsize - sizeof(chunk_list_t);
194  f->overhang = 0;
195  f->next = NULL;
196 
197  __shmem_header->set_free_list_head(f);
198  __shmem_header->set_alloc_list_head(NULL);
199  }
200 
201  __mutex = new Mutex();
202 }
203 
204 
205 /** Destructor */
206 BlackBoardMemoryManager::~BlackBoardMemoryManager()
207 {
208  // close shared memory segment, kill semaphore
209  delete __shmem;
210  delete __shmem_header;
211  if (__memory) {
212  ::free(__memory);
213  }
214  delete __mutex;
215 }
216 
217 
218 /** Allocate memory.
219  * This will allocate memory in the shared memory segment. The strategy is described
220  * in the class description. Note: this method does NOT lock the shared memory
221  * system. Chaos and havoc will come down upon you if you do not ensure locking!
222  * @exception OutOfMemoryException thrown if not enough free memory is available to
223  * accommodate a chunk of the desired size
224  * @param num_bytes number of bytes to allocate
225  * @return pointer to the memory chunk
226  */
227 void *
228 BlackBoardMemoryManager::alloc_nolock(unsigned int num_bytes)
229 {
230  // search for smallest chunk just big enough for desired size
231  chunk_list_t *l = __shmem ? __shmem_header->free_list_head() : __free_list_head;
232 
233  // Note: free chunks list sorted ascending by ptr
234  chunk_list_t *f = NULL;
235  while ( l ) {
236  if ( (l->size >= num_bytes) && // chunk is big enough
237  ( (f == NULL) || (l->size < f->size) ) ) { // no chunk found or current chunk smaller
238  f = l;
239  }
240  l = chunk_ptr(l->next);
241  }
242 
243  if ( f == NULL ) {
244  // Doh, did not find chunk
245  throw OutOfMemoryException("BlackBoard ran out of memory");
246  }
247 
248  // remove chunk from free_list
249  if ( __shmem ) {
250  __shmem_header->set_free_list_head( list_remove(__shmem_header->free_list_head(), f) );
251  } else {
252  __free_list_head = list_remove(__free_list_head, f);
253  }
254 
255  /*
256  // only chunk's semaphore
257  if ( ptr_sems.find( f->ptr ) != ptr_sems.end() ) {
258  SemaphoreSet *s = ptr_sems[f->ptr];
259  delete s;
260  ptr_sems.erase( f->ptr );
261  f->semset_key = 0;
262  }
263  */
264 
265  // our old free list chunk is now our new alloc list chunk
266  // check if there is free space beyond the requested size that makes it worth
267  // entering it into the free list
268  if ( f->size >= (num_bytes + BBMM_MIN_FREE_CHUNK_SIZE + sizeof(chunk_list_t)) ) {
269  // we will have a new free chunk afterwards
270  chunk_list_t *nfc = (chunk_list_t *)((char *)f + sizeof(chunk_list_t) + num_bytes);
271  nfc->ptr = __shmem ? __shmem->addr((char *)nfc + sizeof(chunk_list_t)) : (char *)nfc + sizeof(chunk_list_t);
272  nfc->size = f->size - num_bytes - sizeof(chunk_list_t);
273  nfc->overhang = 0;
274 
275  if ( __shmem ) {
276  __shmem_header->set_free_list_head( list_add(__shmem_header->free_list_head(), nfc) );
277  } else {
278  __free_list_head = list_add(__free_list_head, nfc);
279  }
280 
281  f->size = num_bytes;
282  } else {
283  // chunk is too small for another free chunk, now we have allocated but unusued
284  // space, this is ok but not desireable
285  // this is only informational!
286  f->overhang = f->size - num_bytes;
287  }
288 
289  // alloc new chunk
290  if ( __shmem ) {
291  __shmem_header->set_alloc_list_head( list_add(__shmem_header->alloc_list_head(), f) );
292  return __shmem->ptr(f->ptr);
293  } else {
294  __alloc_list_head = list_add(__alloc_list_head, f);
295  return f->ptr;
296  }
297 
298 }
299 
300 
301 /** Allocate memory.
302  * This will allocate memory in the shared memory segment. The strategy is described
303  * in the class description.
304  * @exception OutOfMemoryException thrown if not enough free memory is available to
305  * accommodate a chunk of the desired size
306  * @param num_bytes number of bytes to allocate
307  * @return pointer to the memory chunk
308  */
309 void *
310 BlackBoardMemoryManager::alloc(unsigned int num_bytes)
311 {
312  void * ptr;
313  __mutex->lock();
314  if (__shmem) __shmem->lock_for_write();
315  try {
316  ptr = alloc_nolock(num_bytes);
317  } catch (Exception &e) {
318  if (__shmem) __shmem->unlock();
319  __mutex->unlock();
320  throw;
321  }
322  if (__shmem) __shmem->unlock();
323  __mutex->unlock();
324  return ptr;
325 }
326 
327 
328 /** Free a memory chunk.
329  * Frees a previously allocated chunk. Not that you have to give the exact pointer
330  * that was returned by alloc(). You may not give a pointer inside a memory chunk or
331  * even worse outside of it! See the class description for a brief description of
332  * the strategy used.
333  * @param ptr pointer to the chunk of memory
334  * @exception BlackBoardMemMgrInvalidPointerException a pointer that has not been
335  * previously returned by alloc() has been given and could not be found in the
336  * allocated chunks list.
337  */
338 void
339 BlackBoardMemoryManager::free(void *ptr)
340 {
341  __mutex->lock();
342  if (__shmem) {
343  __shmem->lock_for_write();
344 
345  // find chunk in alloc_chunks
346  chunk_list_t *ac = list_find_ptr(__shmem_header->alloc_list_head(), chunk_addr(ptr));
347  if ( ac == NULL ) {
349  }
350 
351  // remove from alloc_chunks
352  __shmem_header->set_alloc_list_head( list_remove(__shmem_header->alloc_list_head(), ac) );
353 
354  // reclaim as free memory
355  ac->overhang = 0;
356  __shmem_header->set_free_list_head( list_add(__shmem_header->free_list_head(), ac) );
357 
358  // merge adjacent regions
359  cleanup_free_chunks();
360 
361  __shmem->unlock();
362  } else {
363  // find chunk in alloc_chunks
364  chunk_list_t *ac = list_find_ptr(__alloc_list_head, ptr);
365  if ( ac == NULL ) {
367  }
368 
369  // remove from alloc_chunks
370  __alloc_list_head = list_remove(__alloc_list_head, ac);
371 
372  // reclaim as free memory
373  ac->overhang = 0;
374  __free_list_head = list_add(__free_list_head, ac);
375 
376  // merge adjacent regions
377  cleanup_free_chunks();
378  }
379 
380  __mutex->unlock();
381 }
382 
383 
384 /** Check memory consistency.
385  * This method checks the consistency of the memory segment. It controls whether
386  * all the memory is covered by the free and allocated chunks lists and if there is
387  * no unmanaged memory between chunks.
388  * @exception BBInconsistentMemoryException thrown if the memory segment has been
389  * corrupted. Contains descriptive message.
390  */
391 void
392 BlackBoardMemoryManager::check()
393 {
394  chunk_list_t *f = __shmem ? __shmem_header->free_list_head() : __free_list_head;
395  chunk_list_t *a = __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head;
396  chunk_list_t *t = NULL;
397 
398  unsigned int mem = 0;
399 
400  // we crawl through the memory and analyse if the chunks are continuous,
401  // assumption: chunk list sorted ascending by ptr
402  while ( f || a ) {
403  if ( f == NULL ) {
404  mem += a->size + sizeof(chunk_list_t);
405  t = chunk_ptr(a->next);
406  if ( t ) {
407  // check if a is continuous
408  void *next = (char *)a->ptr + a->size + sizeof(chunk_list_t);
409  if ( next != t->ptr ) {
410  throw BBInconsistentMemoryException("non-contiguos allocated memory");
411  }
412  }
413  a = t;
414  } else if ( a == NULL ) {
415  mem += f->size + sizeof(chunk_list_t);
416  t = chunk_ptr(f->next);
417  if ( t ) {
418  // check if f is continuous
419  void *next = (char *)f->ptr + f->size + sizeof(chunk_list_t);
420  if ( next != t->ptr ) {
421  throw BBInconsistentMemoryException("non-contiguos allocated memory");
422  }
423  }
424  f = t;
425  } else if ( f->ptr == a->ptr ) {
426  throw BBInconsistentMemoryException("ptr cannot be free and allocated at the same time");
427  } else if ( f->ptr < a->ptr ) {
428  mem += f->size + sizeof(chunk_list_t);
429  void *next = (char *)f->ptr + f->size;
430  t = chunk_ptr(f->next);
431  if ( (next != t) && (next != a) ) {
432  throw BBInconsistentMemoryException("there are unallocated bytes between chunks (f)");
433  }
434  f = t;
435  } else {
436  mem += a->size + sizeof(chunk_list_t);
437  void *next = (char *)a->ptr + a->size;
438  t = chunk_ptr(a->next);
439  if ( (next != t) && (next != f) ) {
440  throw BBInconsistentMemoryException("there are unallocated bytes between chunks (a)");
441  }
442  a = t;
443  }
444  }
445 
446  if ( mem != __memsize ) {
447  throw BBInconsistentMemoryException("unmanaged memory found, managed memory size != total memory size");
448  }
449 }
450 
451 
452 /** Check if this BB memory manager is the master.
453  * @return true if this BB memory manager instance is the master for the BB
454  * shared memory segment, false otherwise
455  */
456 bool
457 BlackBoardMemoryManager::is_master() const
458 {
459  return __master;
460 }
461 
462 
463 /** Print out info about free chunks.
464  * Prints out a formatted list of free chunks.
465  */
466 void
467 BlackBoardMemoryManager::print_free_chunks_info() const
468 {
469  list_print_info( __shmem ? __shmem_header->free_list_head() : __free_list_head );
470 }
471 
472 
473 /** Print out info about allocated chunks.
474  * Prints out a formatted list of allocated chunks.
475  */
476 void
477 BlackBoardMemoryManager::print_allocated_chunks_info() const
478 {
479  list_print_info( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head );
480 }
481 
482 
483 /** Prints out performance info.
484  * This will print out information about the number of free and allocated chunks,
485  * the maximum free and allocated chunk size and the number of overhanging bytes
486  * (see class description about overhanging bytes).
487  */
488 void
489 BlackBoardMemoryManager::print_performance_info() const
490 {
491  printf("free chunks: %6u, alloc chunks: %6u, max free: %10u, max alloc: %10u, overhang: %10u\n",
492  list_length( __shmem ? __shmem_header->free_list_head() : __free_list_head),
493  list_length( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head),
494  max_free_size(), max_allocated_size(), overhang_size());
495 }
496 
497 
498 /** Get maximum allocatable memory size.
499  * This method gives information about the maximum free chunk size and thus
500  * the maximum of memory that can be allocated in one chunk.
501  * @return maximum free chunk size
502  */
503 unsigned int
504 BlackBoardMemoryManager::max_free_size() const
505 {
506  chunk_list_t *m = list_get_biggest( __shmem ? __shmem_header->free_list_head() : __free_list_head );
507  if ( m == NULL ) {
508  return 0;
509  } else {
510  return m->size;
511  }
512 }
513 
514 
515 /** Get total free memory.
516  * This method gives information about the sum of all free chunk sizes. Note that
517  * it is not guaranteed that that much data can be stored in the memory since
518  * fragmentation may have occured. To get information about the biggest piece
519  * of memory that you can allocate use getMaxFreeSize()
520  * @return sum of free chunk sizes
521  */
522 unsigned int
523 BlackBoardMemoryManager::free_size() const
524 {
525  unsigned int free_size = 0;
526  chunk_list_t *l = __shmem ? __shmem_header->free_list_head() : __free_list_head;
527  while ( l ) {
528  free_size += l->size;
529  l = chunk_ptr(l->next);
530  }
531  return free_size;
532 }
533 
534 
535 /** Get total allocated memory.
536  * This method gives information about the sum of all allocated chunk sizes.
537  * @return sum of allocated chunks sizes
538  */
539 unsigned int
540 BlackBoardMemoryManager::allocated_size() const
541 {
542  unsigned int alloc_size = 0;
543  chunk_list_t *l = __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head;
544  while ( l ) {
545  alloc_size += l->size;
546  l = chunk_ptr(l->next);
547  }
548  return alloc_size;
549 }
550 
551 
552 /** Get number of allocated chunks.
553  * @return number of allocated memory chunks
554  */
555 unsigned int
556 BlackBoardMemoryManager::num_allocated_chunks() const
557 {
558  return list_length( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head );
559 }
560 
561 
562 /** Get number of free chunks.
563  * @return number of free memory chunks
564  */
565 unsigned int
566 BlackBoardMemoryManager::num_free_chunks() const
567 {
568  return list_length( __shmem ? __shmem_header->free_list_head() : __free_list_head );
569 }
570 
571 
572 /** Get size of memory.
573  * This does not include memory headers, but only the size of the data segment.
574  * @return size of memory.
575  */
576 unsigned int
577 BlackBoardMemoryManager::memory_size() const
578 {
579  return __memsize;
580 }
581 
582 
583 /** Get BlackBoard version.
584  * @return BlackBoard version
585  */
586 unsigned int
587 BlackBoardMemoryManager::version() const
588 {
589  return __shmem ? __shmem_header->version() : 0;
590 }
591 
592 
593 /** Lock memory.
594  * Locks the whole memory segment used and managed by the memory manager. Will
595  * aquire local mutex lock and global semaphore lock in shared memory segment.
596  */
597 void
598 BlackBoardMemoryManager::lock()
599 {
600  __mutex->lock();
601  if (__shmem) __shmem->lock_for_write();
602 }
603 
604 
605 /** Try to lock memory.
606  * Tries to lock the whole memory segment used and managed by the memory manager. Will
607  * aquire local mutex lock and global semaphore lock in shared memory segment.
608  * The lock has been successfully aquired if both of these locks could be aquired!
609  * @return true, if the lock could be aquired, false otherwise.
610  */
611 bool
612 BlackBoardMemoryManager::try_lock()
613 {
614  if ( __mutex->try_lock() ) {
615  if (__shmem) {
616  if ( __shmem->try_lock_for_write() ) {
617  return true;
618  } else {
619  __mutex->unlock();
620  }
621  } else {
622  return true;
623  }
624  }
625 
626  return false;
627 }
628 
629 
630 /** Unlock memory.
631  * Releases the lock hold on the shared memory segment and the local mutex lock.
632  */
633 void
634 BlackBoardMemoryManager::unlock()
635 {
636  if (__shmem) __shmem->unlock();
637  __mutex->unlock();
638 }
639 
640 
641 /** Get maximum alloced memory size.
642  * This method gives information about the maximum allocated chunk size and thus
643  * the maximum of memory that has been be allocated in one chunk.
644  * @return maximum allocated chunk size
645  */
646 unsigned int
647 BlackBoardMemoryManager::max_allocated_size() const
648 {
649  chunk_list_t *m = list_get_biggest( __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head);
650  if ( m == NULL ) {
651  return 0;
652  } else {
653  return m->size;
654  }
655 }
656 
657 
658 /** Get number of overhanging bytes.
659  * The number of overhanging bytes. See class description for more info about
660  * overhanging bytes.
661  * @return number of overhanging bytes
662  */
663 unsigned int
664 BlackBoardMemoryManager::overhang_size() const
665 {
666  unsigned int overhang = 0;
667  chunk_list_t *a = __shmem ? __shmem_header->alloc_list_head() : __alloc_list_head;
668  while ( a ) {
669  overhang += a->overhang;
670  a = chunk_ptr(a->next);
671  }
672  return overhang;
673 }
674 
675 
676 /** Cleanup and merge free chunks.
677  * This will merge adjacent free chunks into one big chunk. After this method ran it
678  * is guaranteed that the maximum available memory resides in one chunk.
679  */
680 void
681 BlackBoardMemoryManager::cleanup_free_chunks()
682 {
683  bool modified = true;
684  chunk_list_t *l;
685  chunk_list_t *n; // next
686 
687  while (modified) {
688  modified = false;
689  l = __shmem ? __shmem_header->free_list_head() : __free_list_head;
690  n = chunk_ptr(l->next);
691  while ( l && n) {
692  if ( ((char *)l->ptr + l->size + sizeof(chunk_list_t)) == n->ptr ) {
693  // re-unite
694  l->size += n->size + sizeof(chunk_list_t);
695  l->next = n->next;
696  modified = true;
697  }
698  l = n;
699  n = chunk_ptr(l->next);
700  }
701  }
702 }
703 
704 
705 /** Remove an element from a list.
706  * @param list list to remove the element from
707  * @param rmel element to remove
708  * @return the head of the new resulting list
709  * @exception NullPointerException thrown if list or rmel equals NULL
710  */
711 chunk_list_t *
712 BlackBoardMemoryManager::list_remove(chunk_list_t *list, chunk_list_t *rmel)
713 {
714  if ( list == NULL )
715  throw NullPointerException("BlackBoardMemoryManager::list_remove: list == NULL");
716  if ( rmel == NULL )
717  throw NullPointerException("BlackBoardMemoryManager::list_remove: rmel == NULL");
718 
719 
720  chunk_list_t *new_head = list;
721  chunk_list_t *l = list;
722  chunk_list_t *p = NULL;
723 
724  while ( l ) {
725  if ( l == rmel ) {
726  // found element, now remove
727  if ( p ) {
728  // we have a predecessor
729  p->next = l->next;
730  } else {
731  // new head
732  new_head = chunk_ptr(l->next);
733  }
734  break;
735  }
736  p = l;
737  l = chunk_ptr(l->next);
738  }
739 
740  return new_head;
741 }
742 
743 
744 /** Add an element to a list.
745  * @param list list to add the element to
746  * @param rmel element to add
747  * @return the head of the new resulting list
748  * @exception NullPointerException thrown if addel equals NULL
749  */
750 chunk_list_t *
751 BlackBoardMemoryManager::list_add(chunk_list_t *list, chunk_list_t *addel)
752 {
753  if ( addel == NULL )
754  throw NullPointerException("BlackBoardMemoryManager::list_add: addel == NULL");
755 
756  chunk_list_t *new_head = list;
757  chunk_list_t *l = list;
758  chunk_list_t *p = NULL;
759 
760  while ( l ) {
761  if ( addel->ptr < l->ptr ) {
762  // add it here
763  addel->next = chunk_addr(l);
764  if ( p != NULL ) {
765  // predecessor needs new successor
766  // before: p->next == l
767  p->next = chunk_addr(addel);
768  } else {
769  new_head = addel;
770  }
771  // used as condition below
772  l = addel;
773  break;
774  } else {
775  p = l;
776  l = chunk_ptr(l->next);
777  }
778  }
779 
780  // if l is not addel it has not yet been added
781  if ( l != addel ) {
782  // p is last element of list and != NULL
783  addel->next = NULL;
784  if ( p ) {
785  p->next = chunk_addr(addel);
786  } else {
787  new_head = addel;
788  }
789  }
790 
791  return new_head;
792 }
793 
794 
795 /** Find a chunk by ptr.
796  * @param list list to search
797  * @param ptr Pointer to search for
798  * @return the chunk that points to ptr or NULL if not found
799  */
800 chunk_list_t *
801 BlackBoardMemoryManager::list_find_ptr(chunk_list_t *list, void *ptr)
802 {
803  chunk_list_t *l = list;
804  while ( l ) {
805  if ( l->ptr == ptr ) {
806  // found it
807  return l;
808  } else {
809  l = chunk_ptr(l->next);
810  }
811  }
812  return NULL;
813 }
814 
815 
816 /** Print info about chunks in list.
817  * Will print information about chunks in list to stdout. Will give pointer as hexadezimal
818  * number, size and overhanging bytes of chunk
819  * @param list list with chunks to print
820  */
821 void
822 BlackBoardMemoryManager::list_print_info(const chunk_list_t *list) const
823 {
824  chunk_list_t *l = (chunk_list_t *)list;
825  unsigned int i = 0;
826 
827  while ( l ) {
828  printf("Chunk %3u: 0x%x size=%10u bytes overhang=%10u bytes\n",
829  ++i, (unsigned int)(size_t)l->ptr, l->size, l->overhang);
830  l = chunk_ptr(l->next);
831  }
832 
833 }
834 
835 
836 /** Get length of list.
837  * @param list list to count
838  * @return length of list
839  */
840 unsigned int
841 BlackBoardMemoryManager::list_length(const chunk_list_t *list) const
842 {
843  unsigned int l = 0;
844  while ( list ) {
845  ++l;
846  list = chunk_ptr(list->next);
847  }
848  return l;
849 }
850 
851 
852 /** Get biggest chunk from list.
853  * @param list list to search
854  * @return biggest chunk in list
855  */
856 chunk_list_t *
857 BlackBoardMemoryManager::list_get_biggest(const chunk_list_t *list) const
858 {
859  chunk_list_t *b = (chunk_list_t *)list;
860  chunk_list_t *l = (chunk_list_t *)list;
861  while ( l ) {
862  if ( l->size > b->size ) {
863  b = l;
864  }
865  l = chunk_ptr(l->next);
866  }
867 
868  return b;
869 }
870 
871 /** Get first element for chunk iteration.
872  * @return Iterator pointing to first memory chunk
873  */
874 BlackBoardMemoryManager::ChunkIterator
875 BlackBoardMemoryManager::begin()
876 {
877  if (__shmem) {
878  return BlackBoardMemoryManager::ChunkIterator(__shmem, __shmem_header->alloc_list_head() );
879  } else {
880  return BlackBoardMemoryManager::ChunkIterator(__alloc_list_head);
881  }
882 }
883 
884 /** Get end of chunk list.
885  * This returns an iterator that points to the element just beyond the allocated
886  * chunk list.
887  * @return ChunkIterator pointing to a non-existant element beyond the chunk list
888  */
890 BlackBoardMemoryManager::end()
891 {
893 }
894 
895 
896 /** @class BlackBoardMemoryManager::ChunkIterator <blackboard/internal/memory_manager.h>
897  * Iterator for memory chunks.
898  * The ChunkIterator can be used to iterate over all allocated memory chunks
899  * in the memory segment.
900  */
901 
902 /** Constructor.
903  * Will create a instance pointing beyond the end of the lits.
904  */
905 BlackBoardMemoryManager::ChunkIterator::ChunkIterator()
906 {
907  __shmem = NULL;
908  __cur = NULL;
909 }
910 
911 /** Constructor
912  * @param shmem shared memory segkent
913  * @param cur Current element for chunk list
914  */
915 BlackBoardMemoryManager::ChunkIterator::ChunkIterator(SharedMemory *shmem,
916  chunk_list_t *cur)
917 {
918  __shmem = shmem;
919  __cur = cur;
920 }
921 
922 
923 /** Constructor
924  * @param cur Current element for chunk list
925  */
926 BlackBoardMemoryManager::ChunkIterator::ChunkIterator(chunk_list_t *cur)
927 {
928  __shmem = NULL;
929  __cur = cur;
930 }
931 
932 
933 /** Copy constructor.
934  * @param it Iterator to copy
935  */
936 BlackBoardMemoryManager::ChunkIterator::ChunkIterator(const ChunkIterator &it)
937 {
938  __shmem = it.__shmem;
939  __cur = it.__cur;
940 }
941 
942 
943 /** Increment iterator.
944  * Advances to the next element. This is the infix-operator. It may be used
945  * like this:
946  * @code
947  * for (ChunkIterator cit = memmgr->begin(); cit != memmgr->end(); ++cit) {
948  * // your code here
949  * }
950  * @endcode
951  * @return Reference to instance itself after advancing to the next element.
952  */
954 BlackBoardMemoryManager::ChunkIterator::operator++()
955 {
956  if ( __cur != NULL ) __cur = chunk_ptr(__cur->next);
957 
958  return *this;
959 }
960 
961 
962 /** Increment iterator.
963  * Advances to the next element in allocated chunk list. This is the postfix-operator.
964  * It may be used like this:
965  * @code
966  * for (ChunkIterator cit = memmgr->begin(); cit != memmgr->end(); cit++) {
967  * // your code here
968  * }
969  * @endcode
970  * Note that since a copy of the original iterator has to be created an returned it
971  * the postfix operation takes both, more CPU time and more memory. If possible (especially
972  * if used in a for loop like the example) use the prefix operator!
973  * @see operator++()
974  * @param inc ignored
975  * @return copy of the current instance before advancing to the next element.
976  */
978 BlackBoardMemoryManager::ChunkIterator::operator++(int inc)
979 {
980  ChunkIterator rv(*this);
981  if ( __cur != NULL ) __cur = chunk_ptr(__cur->next);
982 
983  return rv;
984 }
985 
986 
987 /** Advance by a certain amount.
988  * Can be used to add an integer to the iterator to advance many steps in one go.
989  * This operation takes linear time depending on i.
990  * @param i steps to advance in list. If i is bigger than the number of remaining
991  * elements in the list will stop beyond list.
992  * @return reference to current instance after advancing i steps or after reaching
993  * end of list.
994  */
996 BlackBoardMemoryManager::ChunkIterator::operator+(unsigned int i)
997 {
998  for (unsigned int j = 0; (__cur != NULL) && (j < i); ++j) {
999  if ( __cur != NULL ) __cur = chunk_ptr(__cur->next);
1000  }
1001  return *this;
1002 }
1003 
1004 
1005 /** Advance by a certain amount.
1006  * Works like operator+(unsigned int i), provided for convenience.
1007  * @param i steps to advance in list
1008  * @return reference to current instance after advancing i steps or after reaching
1009  * end of list.
1010  */
1012 BlackBoardMemoryManager::ChunkIterator::operator+=(unsigned int i)
1013 {
1014  for (unsigned int j = 0; (__cur != NULL) && (j < i); ++j) {
1015  if ( __cur != NULL ) __cur = chunk_ptr(__cur->next);
1016  }
1017  return *this;
1018 }
1019 
1020 
1021 /** Check equality of two iterators.
1022  * Can be used to determine if two iterators point to the same chunk.
1023  * @param c iterator to compare current instance to
1024  * @return true, if iterators point to the same chunk, false otherwise
1025  */
1026 bool
1027 BlackBoardMemoryManager::ChunkIterator::operator==(const ChunkIterator & c) const
1028 {
1029  return (__cur == c.__cur);
1030 }
1031 
1032 
1033 /** Check inequality of two iterators.
1034  * Can be used to determine if two iterators point to different chunks.
1035  * @param c iterator to compare current instance to
1036  * @return true, if iterators point to different chunks of memory, false otherwise
1037  */
1038 bool
1039 BlackBoardMemoryManager::ChunkIterator::operator!=(const ChunkIterator & c) const
1040 {
1041  return (__cur != c.__cur);
1042 }
1043 
1044 
1045 /** Get memory pointer of chunk.
1046  * Use this operator to get the pointer to the chunk of memory that this iterator
1047  * points to.
1048  * @return pointer to memory
1049  */
1050 void *
1051 BlackBoardMemoryManager::ChunkIterator::operator*() const
1052 {
1053  if ( __cur == NULL ) return NULL;
1054 
1055  if (__shmem) return __shmem->ptr(__cur->ptr);
1056  else return __cur->ptr;
1057 }
1058 
1059 
1060 /** Assign iterator.
1061  * Makes the current instance to point to the same memory element as c.
1062  * @param c assign value
1063  * @return reference to current instance
1064  */
1066 BlackBoardMemoryManager::ChunkIterator::operator=(const ChunkIterator & c)
1067 {
1068  __shmem = c.__shmem;
1069  __cur = c.__cur;
1070  return *this;
1071 }
1072 
1073 
1074 /** Get size of data segment.
1075  * Returns the size of the memory chunk. This includes overhanging bytes.
1076  * @return size of chunk including overhanging bytes
1077  */
1078 unsigned int
1079 BlackBoardMemoryManager::ChunkIterator::size() const
1080 {
1081  return ( __cur != NULL ) ? __cur->size : 0;
1082 }
1083 
1084 
1085 /** Get number of overhanging bytes.
1086  * See documentation of BlackBoardMemoryManager about overhanging bytes.
1087  * @see BlackBoardMemoryManager
1088  * @return number of overhanging bytes.
1089  */
1090 unsigned int
1091 BlackBoardMemoryManager::ChunkIterator::overhang() const
1092 {
1093  return ( __cur != NULL ) ? __cur->overhang : 0;
1094 }
1095 
1096 } // end namespace fawkes
Thrown when BlackBoard memory has been corupted This exception is thrown by the memory manager if the...
Definition: exceptions.h:47
chunk_list_t * next
offset to next element in list
unsigned int size
total size of chunk, including overhanging bytes, excluding header
Chunk lists as stored in BlackBoard shared memory segment.
unsigned int overhang
number of overhanging bytes in this chunk
A NULL pointer was supplied where not allowed.
Definition: exceptions.h:35
void * ptr
pointer to data memory
Base class for exceptions in Fawkes.
Definition: exception.h:36
Thrown if shared memory could not be opened.
Definition: exceptions.h:82
Thrown if BlackBoard is not master and master operation has been requested.
Definition: exceptions.h:66
Could not attach to shared memory segment.
Shared memory segment.
Definition: shm.h:49
BlackBoard Shared Memory Header.
Definition: header.h:34
Mutex mutual exclusion lock.
Definition: mutex.h:32