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  */
849 BlackBoardMemoryManager::ChunkIterator
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  */
1018 void *
1020 {
1021  if (cur_ == NULL)
1022  return NULL;
1023 
1024  if (shmem_)
1025  return shmem_->ptr(cur_->ptr);
1026  else
1027  return cur_->ptr;
1028 }
1029 
1030 /** Assign iterator.
1031  * Makes the current instance to point to the same memory element as c.
1032  * @param c assign value
1033  * @return reference to current instance
1034  */
1037 {
1038  shmem_ = c.shmem_;
1039  cur_ = c.cur_;
1040  return *this;
1041 }
1042 
1043 /** Get size of data segment.
1044  * Returns the size of the memory chunk. This includes overhanging bytes.
1045  * @return size of chunk including overhanging bytes
1046  */
1047 unsigned int
1049 {
1050  return (cur_ != NULL) ? cur_->size : 0;
1051 }
1052 
1053 /** Get number of overhanging bytes.
1054  * See documentation of BlackBoardMemoryManager about overhanging bytes.
1055  * @see BlackBoardMemoryManager
1056  * @return number of overhanging bytes.
1057  */
1058 unsigned int
1060 {
1061  return (cur_ != NULL) ? cur_->overhang : 0;
1062 }
1063 
1064 } // end namespace fawkes
Thrown when BlackBoard memory has been corupted This exception is thrown by the memory manager if the...
Definition: exceptions.h:50
Thrown if shared memory could not be opened.
Definition: exceptions.h:84
Thrown if BlackBoard is not master and master operation has been requested.
Definition: exceptions.h:69
A NULL pointer was supplied where not allowed.
Definition: exceptions.h:36
unsigned int size() const
Get size of data segment.
bool operator!=(const ChunkIterator &c) const
Check inequality of two iterators.
bool operator==(const ChunkIterator &c) const
Check equality of two iterators.
ChunkIterator & operator=(const ChunkIterator &c)
Assign iterator.
unsigned int overhang() const
Get number of overhanging bytes.
ChunkIterator & operator++()
Increment iterator.
ChunkIterator & operator+=(unsigned int i)
Advance by a certain amount.
void * operator*() const
Get memory pointer of chunk.
ChunkIterator & operator+(unsigned int i)
Advance by a certain amount.
unsigned int overhang_size() const
Get number of overhanging bytes.
unsigned int num_free_chunks() const
Get number of free chunks.
void * alloc(unsigned int num_bytes)
Allocate memory.
void print_free_chunks_info() const
Print out info about free chunks.
void print_allocated_chunks_info() const
Print out info about allocated chunks.
unsigned int memory_size() const
Get size of memory.
void free(void *chunk_ptr)
Free a memory chunk.
unsigned int max_free_size() const
Get maximum allocatable memory size.
ChunkIterator end()
Get end of chunk list.
void check()
Check memory consistency.
bool try_lock()
Try to lock memory.
void print_performance_info() const
Prints out performance info.
ChunkIterator begin()
Get first element for chunk iteration.
unsigned int allocated_size() const
Get total allocated memory.
unsigned int free_size() const
Get total free memory.
unsigned int version() const
Get BlackBoard version.
BlackBoardMemoryManager(size_t memsize)
Heap Memory Constructor.
unsigned int num_allocated_chunks() const
Get number of allocated chunks.
unsigned int max_allocated_size() const
Get maximum alloced memory size.
bool is_master() const
Check if this BB memory manager is the master.
BlackBoard Shared Memory Header.
Definition: header.h:35
void set_shared_memory(SharedMemory *shmem)
Set SharedMemory instance.
Definition: header.cpp:83
unsigned int version() const
Get BlackBoard version.
Definition: header.cpp:224
chunk_list_t * free_list_head()
Get the head of the free chunks list.
Definition: header.cpp:185
void set_free_list_head(chunk_list_t *flh)
Set the head of the free chunks list.
Definition: header.cpp:205
void set_alloc_list_head(chunk_list_t *alh)
Set the head of the allocated chunks list.
Definition: header.cpp:215
chunk_list_t * alloc_list_head()
Get the head of the allocated chunks list.
Definition: header.cpp:195
Base class for exceptions in Fawkes.
Definition: exception.h:36
Mutex mutual exclusion lock.
Definition: mutex.h:33
bool try_lock()
Tries to lock the mutex.
Definition: mutex.cpp:117
void lock()
Lock this mutex.
Definition: mutex.cpp:87
void unlock()
Unlock the mutex.
Definition: mutex.cpp:131
Shared memory segment.
Definition: shm.h:53
void * addr(void *ptr) const
Get an address from a real pointer.
Definition: shm.cpp:690
bool is_valid() const
Check validity of shared memory segment.
Definition: shm.cpp:811
void add_semaphore()
Add semaphore to shared memory segment.
Definition: shm.cpp:852
void lock_for_write()
Lock shared memory segment for writing.
Definition: shm.cpp:959
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:734
void * ptr(void *addr) const
Get the real pointer to the data based on an address.
Definition: shm.cpp:659
void unlock()
Unlock memory.
Definition: shm.cpp:1025
bool try_lock_for_write()
Try to aquire lock on shared memory segment for writing.
Definition: shm.cpp:993
void set_destroy_on_delete(bool destroy)
Set deletion behaviour.
Definition: shm.cpp:839
void set_swapable(bool swapable)
Set shared memory swapable.
Definition: shm.cpp:890
bool is_creator() const
Determine if the shared memory segment has been created by this instance.
Definition: shm.cpp:722
Could not attach to shared memory segment.
Fawkes library namespace.
Chunk lists as stored in BlackBoard shared memory segment.
unsigned int size
total size of chunk, including overhanging bytes, excluding header
chunk_list_t * next
offset to next element in list
unsigned int overhang
number of overhanging bytes in this chunk
void * ptr
pointer to data memory