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