env_alloc.c

Go to the documentation of this file.
00001 /*!@file Envision/env_alloc.c memory allocation routines for 16-byte alignment */
00002 
00003 // //////////////////////////////////////////////////////////////////// //
00004 // The iLab Neuromorphic Vision C++ Toolkit - Copyright (C) 2000-2005   //
00005 // by the University of Southern California (USC) and the iLab at USC.  //
00006 // See http://iLab.usc.edu for information about this project.          //
00007 // //////////////////////////////////////////////////////////////////// //
00008 // Major portions of the iLab Neuromorphic Vision Toolkit are protected //
00009 // under the U.S. patent ``Computation of Intrinsic Perceptual Saliency //
00010 // in Visual Environments, and Applications'' by Christof Koch and      //
00011 // Laurent Itti, California Institute of Technology, 2001 (patent       //
00012 // pending; application number 09/912,225 filed July 23, 2001; see      //
00013 // http://pair.uspto.gov/cgi-bin/final/home.pl for current status).     //
00014 // //////////////////////////////////////////////////////////////////// //
00015 // This file is part of the iLab Neuromorphic Vision C++ Toolkit.       //
00016 //                                                                      //
00017 // The iLab Neuromorphic Vision C++ Toolkit is free software; you can   //
00018 // redistribute it and/or modify it under the terms of the GNU General  //
00019 // Public License as published by the Free Software Foundation; either  //
00020 // version 2 of the License, or (at your option) any later version.     //
00021 //                                                                      //
00022 // The iLab Neuromorphic Vision C++ Toolkit is distributed in the hope  //
00023 // that it will be useful, but WITHOUT ANY WARRANTY; without even the   //
00024 // implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR      //
00025 // PURPOSE.  See the GNU General Public License for more details.       //
00026 //                                                                      //
00027 // You should have received a copy of the GNU General Public License    //
00028 // along with the iLab Neuromorphic Vision C++ Toolkit; if not, write   //
00029 // to the Free Software Foundation, Inc., 59 Temple Place, Suite 330,   //
00030 // Boston, MA 02111-1307 USA.                                           //
00031 // //////////////////////////////////////////////////////////////////// //
00032 //
00033 // Primary maintainer for this file: Rob Peters <rjpeters at usc dot edu>
00034 // $HeadURL: svn://isvn.usc.edu/software/invt/trunk/saliency/src/Envision/env_alloc.c $
00035 // $Id: env_alloc.c 8338 2007-05-04 00:59:03Z rjpeters $
00036 //
00037 
00038 #ifndef ENVISION_ENV_ALLOC_C_DEFINED
00039 #define ENVISION_ENV_ALLOC_C_DEFINED
00040 
00041 #include "Envision/env_alloc.h"
00042 
00043 #include "Envision/env_log.h"
00044 
00045 #define NALIGN ((env_size_t)((4*sizeof(void*)) > 16 ? (4*sizeof(void*)) : 16))
00046 
00047 static env_alloc_func* g_raw_alloc = 0;
00048 static env_dealloc_func* g_raw_dealloc = 0;
00049 static void* g_mutex_userdata = 0;
00050 static env_alloc_mutex_func* g_mutex_acquire = 0;
00051 static env_alloc_mutex_func* g_mutex_release = 0;
00052 
00053 // ######################################################################
00054 /// Free-node class for free-list memory pools.
00055 struct free_list_node
00056 {
00057         struct free_list_node* next;
00058 };
00059 
00060 // ######################################################################
00061 /// Base class for maintaining a free-list memory pool.
00062 struct free_list
00063 {
00064         struct free_list_node* node_list;
00065         env_size_t num_allocations;
00066         env_size_t alloc_size;
00067         env_size_t num_active;
00068 };
00069 
00070 // ######################################################################
00071 //! Auxiliary information about an aligned memory allocation
00072 struct alloc_info
00073 {
00074         // address of ALLOCATED memory, not the address returned to
00075         // the user:
00076         void* alloc_addr;
00077 
00078         // the freelist from which this memory was allocated, or else
00079         // null:
00080         struct free_list* source;
00081 
00082         // number of bytes ALLOCATED, not the number requested by the
00083         // user:
00084         env_size_t alloc_nbytes;
00085 
00086         char pad[NALIGN
00087                  - sizeof(void*)
00088                  - sizeof(struct free_list*)
00089                  - sizeof(env_size_t)];
00090 };
00091 
00092 // ######################################################################
00093 //! Allocate memory that is aligned on an NALIGN-byte boundary
00094 struct aligned_alloc
00095 {
00096         struct free_list cache[ENV_NCACHE];
00097 
00098         unsigned long long nbytes_alltime;
00099         env_size_t nallocations_alltime;
00100         env_size_t nbytes_current;
00101         env_size_t nallocations_current;
00102 };
00103 
00104 // ######################################################################
00105 // this dummy array is here as a compile-time assertion about
00106 // sizeof(struct alloc_info) -- if it doesn't match our expectations,
00107 // then dummy_array gets a negative array size, which triggers a
00108 // compile error:
00109 typedef char
00110 sizeof_alloc_info_must_equal_NALIGN[(sizeof(struct alloc_info) == NALIGN)
00111                                     ? 1 : -1];
00112 
00113 // ######################################################################
00114 static void env_free_list_init(struct free_list* p, env_size_t size_check)
00115 {
00116         ENV_ASSERT(p->node_list == 0);
00117         ENV_ASSERT(size_check >= sizeof(struct free_list_node));
00118 
00119         p->num_allocations = 0;
00120         p->alloc_size = size_check;
00121         p->num_active = 0;
00122 }
00123 
00124 // ######################################################################
00125 /// Allocate space for a new object.
00126 /** If there are chunks available in the free list, one of those is
00127     returned; otherwise new memory is allocated with
00128     (*g_raw_alloc). */
00129 static void* env_free_list_allocate(struct free_list* p, env_size_t bytes)
00130 {
00131         ENV_ASSERT(bytes == p->alloc_size);
00132         if (p->node_list == 0)
00133         {
00134                 ++p->num_allocations;
00135                 ++p->num_active;
00136                 ENV_ASSERT(g_raw_alloc != 0);
00137                 void* const result = (*g_raw_alloc)(bytes);
00138                 ENV_ASSERT2(result != 0, "Memory allocation failed");
00139                 return result;
00140         }
00141         struct free_list_node* n = p->node_list;
00142         p->node_list = p->node_list->next;
00143         ++p->num_active;
00144         return (void*) n;
00145 }
00146 
00147 // ######################################################################
00148 /// Return an object to the free list.
00149 static void env_free_list_deallocate(struct free_list* p, void* space)
00150 {
00151         struct free_list_node* n = (struct free_list_node*) space;
00152         n->next = p->node_list;
00153         p->node_list = n;
00154         --p->num_active;
00155 }
00156 
00157 // ######################################################################
00158 static void env_free_list_cleanup(struct free_list* p)
00159 {
00160         ENV_ASSERT(p->num_active == 0);
00161 
00162         while (p->node_list)
00163         {
00164                 void* space = p->node_list;
00165                 p->node_list = p->node_list->next;
00166                 ENV_ASSERT(g_raw_dealloc != 0);
00167                 (*g_raw_dealloc)(space);
00168                 --p->num_allocations;
00169         }
00170 
00171         ENV_ASSERT(p->num_allocations == 0);
00172         ENV_ASSERT(p->node_list == 0);
00173 
00174         // now we are back to a pristine state, so forget our size:
00175         p->alloc_size = 0;
00176 }
00177 
00178 // ######################################################################
00179 static void env_aligned_alloc_init(struct aligned_alloc* p)
00180 {
00181         p->nbytes_alltime = 0;
00182         p->nallocations_alltime = 0;
00183         p->nbytes_current = 0;
00184         p->nallocations_current = 0;
00185 
00186         for (env_size_t i = 0; i < ENV_NCACHE; ++i)
00187         {
00188                 p->cache[i].node_list = 0;
00189                 p->cache[i].num_allocations = 0;
00190                 p->cache[i].alloc_size = 0;
00191                 p->cache[i].num_active = 0;
00192         }
00193 }
00194 
00195 // ######################################################################
00196 static void env_aligned_alloc_get_stats(const struct aligned_alloc* p,
00197                                         struct env_alloc_stats* stats)
00198 {
00199         stats->nalign = NALIGN;
00200         stats->ncache_used = 0;
00201         stats->nbytes_alltime = p->nbytes_alltime;
00202         stats->nallocations_alltime = p->nallocations_alltime;
00203         stats->nbytes_current = p->nbytes_current;
00204         stats->nallocations_current = p->nallocations_current;
00205         stats->bytes_allocated = 0;
00206         stats->overhead = 2*NALIGN;
00207 
00208         for (env_size_t i = 0; i < ENV_NCACHE; ++i)
00209                 if (p->cache[i].alloc_size > 0)
00210                 {
00211                         ++stats->ncache_used;
00212                         const env_size_t nb =
00213                                 (p->cache[i].num_allocations
00214                                  * p->cache[i].alloc_size);
00215 
00216                         stats->bytes_allocated += nb;
00217 
00218                         stats->cache[i].num_allocations =
00219                                 p->cache[i].num_allocations;
00220                         stats->cache[i].alloc_size =
00221                                 p->cache[i].alloc_size;
00222                         stats->cache[i].num_active =
00223                                 p->cache[i].num_active;
00224                 }
00225 }
00226 
00227 // ######################################################################
00228 static void* env_aligned_alloc_allocate(struct aligned_alloc* p, env_size_t user_nbytes)
00229 {
00230         struct alloc_info info = { 0, 0, 0, { 0 } };
00231         info.source = 0;
00232 
00233         // We request extra space beyond what the user wants -- NALIGN
00234         // extra bytes allow us to return an address to the user that
00235         // is aligned to a NALIGN-byte boundary, and sizeof(struct
00236         // alloc_info) extra bytes allow us to stick some auxiliary
00237         // info just ahead of the address that we return to the
00238         // user. Note that for convenience we have set things up so
00239         // that sizeof(struct alloc_info)==NALIGN, so the number of
00240         // extra bytes that we need is just 2*NALIGN.
00241         info.alloc_nbytes = user_nbytes+2*NALIGN;
00242         info.alloc_addr = 0;
00243 
00244         for (env_size_t i = 0; i < ENV_NCACHE; ++i)
00245         {
00246                 if (p->cache[i].alloc_size > 0)
00247                 {
00248                         // we found a filled slot, but if it doesn't
00249                         // match our requested size then we just skip
00250                         // over it:
00251                         if (p->cache[i].alloc_size != info.alloc_nbytes)
00252                                 continue;
00253                 }
00254                 else
00255                 {
00256                         // we found an empty slot, so let's initialize
00257                         // a new free list for our requested size:
00258                         env_free_list_init(&p->cache[i], info.alloc_nbytes);
00259                 }
00260 
00261                 // now, one way or the other we know that the slot
00262                 // matches our requested size, so go ahead and request
00263                 // an allocation:
00264                 info.source = &p->cache[i];
00265                 info.alloc_addr =
00266                         env_free_list_allocate(&p->cache[i], info.alloc_nbytes);
00267                 break;
00268         }
00269 
00270         if (info.alloc_addr == 0)
00271         {
00272                 info.source = 0;
00273                 ENV_ASSERT(g_raw_alloc != 0);
00274                 info.alloc_addr = (*g_raw_alloc)(info.alloc_nbytes);
00275                 ENV_ASSERT2(info.alloc_addr != 0,
00276                             "Memory allocation failed");
00277         }
00278 
00279         /* We will set things up like this:
00280 
00281         +- address = value of info.alloc_addr
00282         |
00283         |                                        +- address = return value
00284         |                                        |     of this function
00285         v                                        v
00286 
00287         +---------------+------------------------+------------------------+
00288         | len==adjust   | len==NALIGN            | len==user_nbytes       |
00289         | contents:     | contents:              | contents:              |
00290         |   unused      |   struct alloc_info    |   empty space for user |
00291         | alignment:    | alignment:             | alignment:             |
00292         |   unknown     |   NALIGN-byte boundary |   NALIGN-byte boundary |
00293         +---------------+------------------------+------------------------+
00294 
00295         */
00296 
00297         void* const user_addr =
00298                 ((char*) info.alloc_addr)
00299                 + (2*NALIGN)
00300                 - ((unsigned long) info.alloc_addr) % NALIGN;
00301 
00302         ((struct alloc_info*) user_addr)[-1] = info;
00303 
00304         p->nbytes_alltime += info.alloc_nbytes;
00305         ++p->nallocations_alltime;
00306         p->nbytes_current += info.alloc_nbytes;
00307         ++p->nallocations_current;
00308 
00309         return user_addr;
00310 }
00311 
00312 // ######################################################################
00313 static void env_aligned_alloc_deallocate(struct aligned_alloc* p, void* user_addr)
00314 {
00315         const struct alloc_info* const info =
00316                 ((struct alloc_info*) user_addr) - 1;
00317 
00318         p->nbytes_current -= info->alloc_nbytes;
00319         --p->nallocations_current;
00320 
00321         // deallocate memory from the given free_list, otherwise free it
00322         // globally
00323         if (info->source != 0)
00324         {
00325                 env_free_list_deallocate(info->source, info->alloc_addr);
00326         }
00327         else
00328         {
00329                 ENV_ASSERT(g_raw_dealloc != 0);
00330                 (*g_raw_dealloc)(info->alloc_addr);
00331         }
00332 }
00333 
00334 // ######################################################################
00335 static void env_aligned_alloc_cleanup(struct aligned_alloc* p)
00336 {
00337         for (env_size_t i = 0; i < ENV_NCACHE; ++i)
00338                 env_free_list_cleanup(&p->cache[i]);
00339 }
00340 
00341 // ######################################################################
00342 struct aligned_alloc g_alloc;
00343 
00344 // ######################################################################
00345 void* env_allocate(env_size_t user_nbytes)
00346 {
00347         if (g_mutex_acquire) (*g_mutex_acquire)(g_mutex_userdata);
00348         void* ret = env_aligned_alloc_allocate(&g_alloc, user_nbytes);
00349         if (g_mutex_release) (*g_mutex_release)(g_mutex_userdata);
00350         return ret;
00351 }
00352 
00353 // ######################################################################
00354 void env_deallocate(void* mem)
00355 {
00356         if (mem)
00357         {
00358                 if (g_mutex_acquire) (*g_mutex_acquire)(g_mutex_userdata);
00359                 env_aligned_alloc_deallocate(&g_alloc, mem);
00360                 if (g_mutex_release) (*g_mutex_release)(g_mutex_userdata);
00361         }
00362 }
00363 
00364 // ######################################################################
00365 void env_allocation_get_stats(struct env_alloc_stats* stats)
00366 {
00367         if (g_mutex_acquire) (*g_mutex_acquire)(g_mutex_userdata);
00368         env_aligned_alloc_get_stats(&g_alloc, stats);
00369         if (g_mutex_release) (*g_mutex_release)(g_mutex_userdata);
00370 }
00371 
00372 // ######################################################################
00373 void env_allocation_init(env_alloc_func* alloc_func,
00374                          env_dealloc_func* dealloc_func)
00375 {
00376         if (g_mutex_acquire) (*g_mutex_acquire)(g_mutex_userdata);
00377 
00378         g_raw_alloc = alloc_func;
00379         g_raw_dealloc = dealloc_func;
00380 
00381         env_aligned_alloc_init(&g_alloc);
00382         if (g_mutex_release) (*g_mutex_release)(g_mutex_userdata);
00383 }
00384 
00385 // ######################################################################
00386 void env_allocation_cleanup(void)
00387 {
00388         if (g_mutex_acquire) (*g_mutex_acquire)(g_mutex_userdata);
00389         env_aligned_alloc_cleanup(&g_alloc);
00390         if (g_mutex_release) (*g_mutex_release)(g_mutex_userdata);
00391 }
00392 
00393 // ######################################################################
00394 void env_allocation_init_mutex_funcs(void* userdata,
00395                                      env_alloc_mutex_func* mutex_acquire,
00396                                      env_alloc_mutex_func* mutex_release)
00397 {
00398         g_mutex_userdata = userdata;
00399         g_mutex_acquire = mutex_acquire;
00400         g_mutex_release = mutex_release;
00401 }
00402 
00403 // ######################################################################
00404 /* So things look consistent in everyone's emacs... */
00405 /* Local Variables: */
00406 /* indent-tabs-mode: nil */
00407 /* c-file-style: "linux" */
00408 /* End: */
00409 
00410 #endif // ENVISION_ENV_ALLOC_C_DEFINED
Generated on Sun May 8 08:40:38 2011 for iLab Neuromorphic Vision Toolkit by  doxygen 1.6.3