yaffs_allocator.c

   1 /*
   2  * YAFFS: Yet another Flash File System . A NAND-flash specific file system.
   3  *
   4  * Copyright (C) 2002-2010 Aleph One Ltd.
   5  *   for Toby Churchill Ltd and Brightstar Engineering
   6  *
   7  * Created by Charles Manning <charles@aleph1.co.uk>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU Lesser General Public License version 2.1 as
  11  * published by the Free Software Foundation.
  12  *
  13  * Note: Only YAFFS headers are LGPL, YAFFS C code is covered by GPL.
  14  */
  15
  16
  17 #include "yaffs_allocator.h"
  18 #include "yaffs_guts.h"
  19 #include "yaffs_trace.h"
  20 #include "yportenv.h"
  21
  22 #ifdef CONFIG_YAFFS_YMALLOC_ALLOCATOR
  23
  24 void yaffs_DeinitialiseRawTnodesAndObjects(yaffs_Device *dev)
  25 {
  26         dev = dev;
  27 }
  28
  29 void yaffs_InitialiseRawTnodesAndObjects(yaffs_Device *dev)
  30 {
  31         dev = dev;
  32 }
  33
  34 yaffs_Tnode *yaffs_AllocateRawTnode(yaffs_Device *dev)
  35 {
  36         return (yaffs_Tnode *)YMALLOC(dev->tnodeSize);
  37 }
  38
  39 void yaffs_FreeRawTnode(yaffs_Device *dev, yaffs_Tnode *tn)
  40 {
  41         dev = dev;
  42         YFREE(tn);
  43 }
  44
  45 void yaffs_InitialiseRawObjects(yaffs_Device *dev)
  46 {
  47         dev = dev;
  48 }
  49
  50 void yaffs_DeinitialiseRawObjects(yaffs_Device *dev)
  51 {
  52         dev = dev;
  53 }
  54
  55 yaffs_Object *yaffs_AllocateRawObject(yaffs_Device *dev)
  56 {
  57         dev = dev;
  58         return (yaffs_Object *) YMALLOC(sizeof(yaffs_Object));
  59 }
  60
  61
  62 void yaffs_FreeRawObject(yaffs_Device *dev, yaffs_Object *obj)
  63 {
  64
  65         dev = dev;
  66         YFREE(obj);
  67 }
  68
  69 #else
  70
  71 struct yaffs_TnodeList_struct {
  72         struct yaffs_TnodeList_struct *next;
  73         yaffs_Tnode *tnodes;
  74 };
  75
  76 typedef struct yaffs_TnodeList_struct yaffs_TnodeList;
  77
  78 struct yaffs_ObjectList_struct {
  79         yaffs_Object *objects;
  80         struct yaffs_ObjectList_struct *next;
  81 };
  82
  83 typedef struct yaffs_ObjectList_struct yaffs_ObjectList;
  84
  85
  86 struct yaffs_AllocatorStruct {
  87         int nTnodesCreated;
  88         yaffs_Tnode *freeTnodes;
  89         int nFreeTnodes;
  90         yaffs_TnodeList *allocatedTnodeList;
  91
  92         int nObjectsCreated;
  93         yaffs_Object *freeObjects;
  94         int nFreeObjects;
  95
  96         yaffs_ObjectList *allocatedObjectList;
  97 };
  98
  99 typedef struct yaffs_AllocatorStruct yaffs_Allocator;
 100
 101
 102 static void yaffs_DeinitialiseRawTnodes(yaffs_Device *dev)
 103 {
 104
 105         yaffs_Allocator *allocator = (yaffs_Allocator *)dev->allocator;
 106
 107         yaffs_TnodeList *tmp;
 108
 109         if(!allocator){
 110                 YBUG();
 111                 return;
 112         }
 113
 114         while (allocator->allocatedTnodeList) {
 115                 tmp = allocator->allocatedTnodeList->next;
 116
 117                 YFREE(allocator->allocatedTnodeList->tnodes);
 118                 YFREE(allocator->allocatedTnodeList);
 119                 allocator->allocatedTnodeList = tmp;
 120
 121         }
 122
 123         allocator->freeTnodes = NULL;
 124         allocator->nFreeTnodes = 0;
 125         allocator->nTnodesCreated = 0;
 126 }
 127
 128 static void yaffs_InitialiseRawTnodes(yaffs_Device *dev)
 129 {
 130         yaffs_Allocator *allocator = dev->allocator;
 131
 132         if(allocator){
 133                 allocator->allocatedTnodeList = NULL;
 134                 allocator->freeTnodes = NULL;
 135                 allocator->nFreeTnodes = 0;
 136                 allocator->nTnodesCreated = 0;
 137         } else
 138                 YBUG();
 139 }
 140
 141 static int yaffs_CreateTnodes(yaffs_Device *dev, int nTnodes)
 142 {
 143         yaffs_Allocator *allocator = (yaffs_Allocator *)dev->allocator;
 144         int i;
 145         yaffs_Tnode *newTnodes;
 146         __u8 *mem;
 147         yaffs_Tnode *curr;
 148         yaffs_Tnode *next;
 149         yaffs_TnodeList *tnl;
 150
 151         if(!allocator){
 152                 YBUG();
 153                 return YAFFS_FAIL;
 154         }
 155
 156         if (nTnodes < 1)
 157                 return YAFFS_OK;
 158
 159
 160         /* make these things */
 161
 162         newTnodes = YMALLOC(nTnodes * dev->tnodeSize);
 163         mem = (__u8 *)newTnodes;
 164
 165         if (!newTnodes) {
 166                 T(YAFFS_TRACE_ERROR,
 167                         (TSTR("yaffs: Could not allocate Tnodes" TENDSTR)));
 168                 return YAFFS_FAIL;
 169         }
 170
 171         /* Hook them into the free list */
 172 #if 0
 173         for (i = 0; i < nTnodes - 1; i++) {
 174                 newTnodes[i].internal[0] = &newTnodes[i + 1];
 175 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 176                 newTnodes[i].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
 177 #endif
 178         }
 179
 180         newTnodes[nTnodes - 1].internal[0] = allocator->freeTnodes;
 181 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 182         newTnodes[nTnodes - 1].internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
 183 #endif
 184         allocator->freeTnodes = newTnodes;
 185 #else
 186         /* New hookup for wide tnodes */
 187         for (i = 0; i < nTnodes - 1; i++) {
 188                 curr = (yaffs_Tnode *) &mem[i * dev->tnodeSize];
 189                 next = (yaffs_Tnode *) &mem[(i+1) * dev->tnodeSize];
 190                 curr->internal[0] = next;
 191         }
 192
 193         curr = (yaffs_Tnode *) &mem[(nTnodes - 1) * dev->tnodeSize];
 194         curr->internal[0] = allocator->freeTnodes;
 195         allocator->freeTnodes = (yaffs_Tnode *)mem;
 196
 197 #endif
 198
 199
 200         allocator->nFreeTnodes += nTnodes;
 201         allocator->nTnodesCreated += nTnodes;
 202
 203         /* Now add this bunch of tnodes to a list for freeing up.
 204          * NB If we can't add this to the management list it isn't fatal
 205          * but it just means we can't free this bunch of tnodes later.
 206          */
 207
 208         tnl = YMALLOC(sizeof(yaffs_TnodeList));
 209         if (!tnl) {
 210                 T(YAFFS_TRACE_ERROR,
 211                   (TSTR
 212                    ("yaffs: Could not add tnodes to management list" TENDSTR)));
 213                    return YAFFS_FAIL;
 214         } else {
 215                 tnl->tnodes = newTnodes;
 216                 tnl->next = allocator->allocatedTnodeList;
 217                 allocator->allocatedTnodeList = tnl;
 218         }
 219
 220         T(YAFFS_TRACE_ALLOCATE, (TSTR("yaffs: Tnodes added" TENDSTR)));
 221
 222         return YAFFS_OK;
 223 }
 224
 225
 226 yaffs_Tnode *yaffs_AllocateRawTnode(yaffs_Device *dev)
 227 {
 228         yaffs_Allocator *allocator = (yaffs_Allocator *)dev->allocator;
 229         yaffs_Tnode *tn = NULL;
 230
 231         if(!allocator){
 232                 YBUG();
 233                 return NULL;
 234         }
 235
 236         /* If there are none left make more */
 237         if (!allocator->freeTnodes)
 238                 yaffs_CreateTnodes(dev, YAFFS_ALLOCATION_NTNODES);
 239
 240         if (allocator->freeTnodes) {
 241                 tn = allocator->freeTnodes;
 242 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 243                 if (tn->internal[YAFFS_NTNODES_INTERNAL] != (void *)1) {
 244                         /* Hoosterman, this thing looks like it isn't in the list */
 245                         T(YAFFS_TRACE_ALWAYS,
 246                           (TSTR("yaffs: Tnode list bug 1" TENDSTR)));
 247                 }
 248 #endif
 249                 allocator->freeTnodes = allocator->freeTnodes->internal[0];
 250                 allocator->nFreeTnodes--;
 251         }
 252
 253         return tn;
 254 }
 255
 256 /* FreeTnode frees up a tnode and puts it back on the free list */
 257 void yaffs_FreeRawTnode(yaffs_Device *dev, yaffs_Tnode *tn)
 258 {
 259         yaffs_Allocator *allocator = dev->allocator;
 260
 261         if(!allocator){
 262                 YBUG();
 263                 return;
 264         }
 265
 266         if (tn) {
 267 #ifdef CONFIG_YAFFS_TNODE_LIST_DEBUG
 268                 if (tn->internal[YAFFS_NTNODES_INTERNAL] != 0) {
 269                         /* Hoosterman, this thing looks like it is already in the list */
 270                         T(YAFFS_TRACE_ALWAYS,
 271                           (TSTR("yaffs: Tnode list bug 2" TENDSTR)));
 272                 }
 273                 tn->internal[YAFFS_NTNODES_INTERNAL] = (void *)1;
 274 #endif
 275                 tn->internal[0] = allocator->freeTnodes;
 276                 allocator->freeTnodes = tn;
 277                 allocator->nFreeTnodes++;
 278         }
 279         dev->nCheckpointBlocksRequired = 0; /* force recalculation*/
 280 }
 281
 282
 283
 284 static void yaffs_InitialiseRawObjects(yaffs_Device *dev)
 285 {
 286         yaffs_Allocator *allocator = dev->allocator;
 287
 288         if(allocator) {
 289                 allocator->allocatedObjectList = NULL;
 290                 allocator->freeObjects = NULL;
 291                 allocator->nFreeObjects = 0;
 292         } else
 293                 YBUG();
 294 }
 295
 296 static void yaffs_DeinitialiseRawObjects(yaffs_Device *dev)
 297 {
 298         yaffs_Allocator *allocator = dev->allocator;
 299         yaffs_ObjectList *tmp;
 300
 301         if(!allocator){
 302                 YBUG();
 303                 return;
 304         }
 305
 306         while (allocator->allocatedObjectList) {
 307                 tmp = allocator->allocatedObjectList->next;
 308                 YFREE(allocator->allocatedObjectList->objects);
 309                 YFREE(allocator->allocatedObjectList);
 310
 311                 allocator->allocatedObjectList = tmp;
 312         }
 313
 314         allocator->freeObjects = NULL;
 315         allocator->nFreeObjects = 0;
 316         allocator->nObjectsCreated = 0;
 317 }
 318
 319
 320 static int yaffs_CreateFreeObjects(yaffs_Device *dev, int nObjects)
 321 {
 322         yaffs_Allocator *allocator = dev->allocator;
 323
 324         int i;
 325         yaffs_Object *newObjects;
 326         yaffs_ObjectList *list;
 327
 328         if(!allocator){
 329                 YBUG();
 330                 return YAFFS_FAIL;
 331         }
 332
 333         if (nObjects < 1)
 334                 return YAFFS_OK;
 335
 336         /* make these things */
 337         newObjects = YMALLOC(nObjects * sizeof(yaffs_Object));
 338         list = YMALLOC(sizeof(yaffs_ObjectList));
 339
 340         if (!newObjects || !list) {
 341                 if (newObjects){
 342                         YFREE(newObjects);
 343                         newObjects = NULL;
 344                 }
 345                 if (list){
 346                         YFREE(list);
 347                         list = NULL;
 348                 }
 349                 T(YAFFS_TRACE_ALLOCATE,
 350                   (TSTR("yaffs: Could not allocate more objects" TENDSTR)));
 351                 return YAFFS_FAIL;
 352         }
 353
 354         /* Hook them into the free list */
 355         for (i = 0; i < nObjects - 1; i++) {
 356                 newObjects[i].siblings.next =
 357                                 (struct ylist_head *)(&newObjects[i + 1]);
 358         }
 359
 360         newObjects[nObjects - 1].siblings.next = (void *)allocator->freeObjects;
 361         allocator->freeObjects = newObjects;
 362         allocator->nFreeObjects += nObjects;
 363         allocator->nObjectsCreated += nObjects;
 364
 365         /* Now add this bunch of Objects to a list for freeing up. */
 366
 367         list->objects = newObjects;
 368         list->next = allocator->allocatedObjectList;
 369         allocator->allocatedObjectList = list;
 370
 371         return YAFFS_OK;
 372 }
 373
 374 yaffs_Object *yaffs_AllocateRawObject(yaffs_Device *dev)
 375 {
 376         yaffs_Object *obj = NULL;
 377         yaffs_Allocator *allocator = dev->allocator;
 378
 379         if(!allocator) {
 380                 YBUG();
 381                 return obj;
 382         }
 383
 384         /* If there are none left make more */
 385         if (!allocator->freeObjects)
 386                 yaffs_CreateFreeObjects(dev, YAFFS_ALLOCATION_NOBJECTS);
 387
 388         if (allocator->freeObjects) {
 389                 obj = allocator->freeObjects;
 390                 allocator->freeObjects =
 391                         (yaffs_Object *) (allocator->freeObjects->siblings.next);
 392                 allocator->nFreeObjects--;
 393         }
 394
 395         return obj;
 396 }
 397
 398
 399 void yaffs_FreeRawObject(yaffs_Device *dev, yaffs_Object *obj)
 400 {
 401
 402         yaffs_Allocator *allocator = dev->allocator;
 403
 404         if(!allocator)
 405                 YBUG();
 406         else {
 407                 /* Link into the free list. */
 408                 obj->siblings.next = (struct ylist_head *)(allocator->freeObjects);
 409                 allocator->freeObjects = obj;
 410                 allocator->nFreeObjects++;
 411         }
 412 }
 413
 414 void yaffs_DeinitialiseRawTnodesAndObjects(yaffs_Device *dev)
 415 {
 416         if(dev->allocator){
 417                 yaffs_DeinitialiseRawTnodes(dev);
 418                 yaffs_DeinitialiseRawObjects(dev);
 419
 420                 YFREE(dev->allocator);
 421                 dev->allocator=NULL;
 422         } else
 423                 YBUG();
 424 }
 425
 426 void yaffs_InitialiseRawTnodesAndObjects(yaffs_Device *dev)
 427 {
 428         yaffs_Allocator *allocator;
 429
 430         if(!dev->allocator){
 431                 allocator = YMALLOC(sizeof(yaffs_Allocator));
 432                 if(allocator){
 433                         dev->allocator = allocator;
 434                         yaffs_InitialiseRawTnodes(dev);
 435                         yaffs_InitialiseRawObjects(dev);
 436                 }
 437         } else
 438                 YBUG();
 439 }
 440
 441
 442 #endif