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