Fawkes API  Fawkes Development Version
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  */
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  */
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 */
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
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
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
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
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
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
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),
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
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
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
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
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
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
578 {
579  return __memsize;
580 }
581 
582 
583 /** Get BlackBoard version.
584  * @return BlackBoard version
585  */
586 unsigned int
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
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
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
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
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
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  */
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  */
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  */
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  */
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  */
927 {
928  __shmem = NULL;
929  __cur = cur;
930 }
931 
932 
933 /** Copy constructor.
934  * @param it Iterator to copy
935  */
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  */
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  */
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  */
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  */
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
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
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 *
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  */
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
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
1092 {
1093  return ( __cur != NULL ) ? __cur->overhang : 0;
1094 }
1095 
1096 } // end namespace fawkes
void print_performance_info() const
Prints out performance info.
unsigned int version() const
Get BlackBoard version.
Definition: header.cpp:244
Thrown when BlackBoard memory has been corupted This exception is thrown by the memory manager if the...
Definition: exceptions.h:47
chunk_list_t * alloc_list_head()
Get the head of the allocated chunks list.
Definition: header.cpp:212
unsigned int size() const
Get size of data segment.
ChunkIterator begin()
Get first element for chunk iteration.
void set_shared_memory(SharedMemory *shmem)
Set SharedMemory instance.
Definition: header.cpp:87
unsigned int allocated_size() const
Get total allocated memory.
bool is_master() const
Check if this BB memory manager is the master.
void lock_for_write()
Lock shared memory segment for writing.
Definition: shm.cpp:918
void print_allocated_chunks_info() const
Print out info about allocated chunks.
Fawkes library namespace.
ChunkIterator end()
Get end of chunk list.
void unlock()
Unlock the mutex.
Definition: mutex.cpp:135
bool try_lock_for_write()
Try to aquire lock on shared memory segment for writing.
Definition: shm.cpp:953
chunk_list_t * free_list_head()
Get the head of the free chunks list.
Definition: header.cpp:201
unsigned int memory_size() const
Get size of memory.
void set_alloc_list_head(chunk_list_t *alh)
Set the head of the allocated chunks list.
Definition: header.cpp:234
A NULL pointer was supplied where not allowed.
Definition: software.h:34
chunk_list_t * next
offset to next element in list
void * alloc(unsigned int num_bytes)
Allocate memory.
bool is_creator() const
Determine if the shared memory segment has been created by this instance.
Definition: shm.cpp:670
void * addr(void *ptr) const
Get an address from a real pointer.
Definition: shm.cpp:637
unsigned int size
total size of chunk, including overhanging bytes, excluding header
bool try_lock()
Try to lock memory.
Chunk lists as stored in BlackBoard shared memory segment.
bool is_valid() const
Check validity of shared memory segment.
Definition: shm.cpp:766
unsigned int overhang
number of overhanging bytes in this chunk
BlackBoardMemoryManager(size_t memsize)
Heap Memory Constructor.
A NULL pointer was supplied where not allowed.
Definition: exceptions.h:35
ChunkIterator & operator++()
Increment iterator.
void set_swapable(bool swapable)
Set shared memory swapable.
Definition: shm.cpp:847
unsigned int version() const
Get BlackBoard version.
ChunkIterator & operator+=(unsigned int i)
Advance by a certain amount.
void print_free_chunks_info() const
Print out info about free chunks.
unsigned int num_free_chunks() const
Get number of free chunks.
void * ptr
pointer to data memory
Base class for exceptions in Fawkes.
Definition: exception.h:36
bool operator!=(const ChunkIterator &c) const
Check inequality of two iterators.
Thrown if shared memory could not be opened.
Definition: exceptions.h:82
ChunkIterator & operator+(unsigned int i)
Advance by a certain amount.
void set_free_list_head(chunk_list_t *flh)
Set the head of the free chunks list.
Definition: header.cpp:223
void * ptr(void *addr) const
Get the real pointer to the data based on an address.
Definition: shm.cpp:606
void * memptr() const
Get a pointer to the shared memory This method returns a pointer to the data-segment of the shared me...
Definition: shm.cpp:682
Thrown if BlackBoard is not master and master operation has been requested.
Definition: exceptions.h:66
void * operator*() const
Get memory pointer of chunk.
void set_destroy_on_delete(bool destroy)
Set deletion behaviour.
Definition: shm.cpp:796
Could not attach to shared memory segment.
unsigned int free_size() const
Get total free memory.
bool try_lock()
Tries to lock the mutex.
Definition: mutex.cpp:120
void add_semaphore()
Add semaphore to shared memory segment.
Definition: shm.cpp:810
Shared memory segment.
Definition: shm.h:49
unsigned int overhang() const
Get number of overhanging bytes.
BlackBoard Shared Memory Header.
Definition: header.h:34
void check()
Check memory consistency.
unsigned int max_allocated_size() const
Get maximum alloced memory size.
void free(void *chunk_ptr)
Free a memory chunk.
bool operator==(const ChunkIterator &c) const
Check equality of two iterators.
void lock()
Lock this mutex.
Definition: mutex.cpp:89
Mutex mutual exclusion lock.
Definition: mutex.h:32
unsigned int num_allocated_chunks() const
Get number of allocated chunks.
unsigned int max_free_size() const
Get maximum allocatable memory size.
System ran out of memory and desired operation could not be fulfilled.
Definition: system.h:32
void unlock()
Unlock memory.
Definition: shm.cpp:985
ChunkIterator & operator=(const ChunkIterator &c)
Assign iterator.
unsigned int overhang_size() const
Get number of overhanging bytes.