Subversion Repositories shark

Rev

Rev 229 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
141 trimarchi 1
/*
2
 * Doubly indexed dynamic memory allocator (DIDMA)
3
 * Version 0.61
4
 *
5
 * Written by Miguel Masmano Tello <mmasmano@disca.upv.es>
6
 * Copyright (C) Dec, 2002 OCERA Consortium
7
 * Release under the terms of the GNU General Public License Version 2
8
 * shark porting Trimarchi Michael
9
 */
10
 
11
#include <kernel/func.h>
12
#include "didma.h"
13
#include "queuem.h"
14
#include "i386/bitops.h"
15
#include "i386/bits.h"
16
 
17
#ifndef NULL
18
#define NULL ((void *) 0)
19
#endif // #ifndef NULL
20
 
21
 
22
#define INIT_THREAD_MUTEX()
23
#define THREAD_LOCK()   kern_cli()
24
#define THREAD_UNLOCK() kern_sti()
25
 
26
// u8, u16, u32 are only defined in kernel headers
27
 
28
#define u8 char 
29
#define u16 unsigned short int 
30
#define u32 unsigned int 
31
 
32
#define MAX_SL_LOG2_INDEX 5 // Real value is 2**MAX_SL_INDEX
33
 
34
#define MAX_SL_INDEX (1 << MAX_SL_LOG2_INDEX)
35
 
36
#define F_OK 0
37
#define F_ERROR -1
38
 
39
#define MIN_LOG2_SIZE 5 // 32 bytes
40
#define MAX_LOG2_SIZE MAX_FL_INDEX
41
#define MIN_SIZE (1 << MIN_LOG2_SIZE)
42
#define MAX_SIZE (1 << MAX_LOG2_SIZE)
43
 
44
#define DIDMA__set_bit(num, mem) mem |= (1 << num)
45
#define DIDMA__clear_bit(num, mem) mem &= ~(1 << num)
46
 
47
/*
48
 * First, all necessary TADs are defined
49
 */
50
 
51
 
52
/*
53
 * the follow TAD will be a double level indexed array, the most important
54
 * thing is that the time is limited, it is because this dynamic memory manger
55
 * is designed to run with real time programs.
56
 *
57
 *     First level       Second level
58
 *     it is indexed     it is indexed by 2**n+(2**n/m*index_number)
59
 *     by power of 2        
60
 *                            0             1     m-1        m
61
 *                            ----> NULL   --> NULL          ----> NUL
62
 *                            |            |                 |
63
 *       -------         ---------------------...---------------------
64
 *  2**n |  n  |  -----> |2**n+(2**n/m*0)|...|   |...|2**n+(2**n/m*m)|
65
 *       |-----|         ---------------------...---------------------
66
 * 2**n-1| n-1 |  -----> ....                      |            
67
 *       |-----|                                   --->NULL
68
 *        .....
69
 */
70
 
71
/* DON'T TOUCH THESE MACROS */
72
#define MAGIC_NUMBER 0xA5A5
73
#define MAGIC_NUMBER_NONE 0x0000
74
#define BLOCK_FREE 0
75
#define BLOCK_USED 1
76
 
77
 
78
struct free_ptr_struct {
79
  struct block_header_struct *prev;
80
  struct block_header_struct *next;
81
  /*
82
   * first_l_index and second_l_index are used to store
83
   * mapping_function results, that's how we get some extra
84
   * nanoseconds
85
   */
86
  u8 first_l_index;
87
  u8 second_l_index;
88
};
89
 
90
typedef struct block_header_struct {
91
  /* magic_number is the id of the block */
92
  u16 magic_number;
93
  /* size of the block */
94
  size_t size;
95
  /* state of the block can be free or used */
96
  u8 state;
97
 
98
  struct block_header_struct *prev;
99
  struct block_header_struct *next;
100
 
101
  union {
102
    struct free_ptr_struct free_ptr;
103
    u8 buffer[sizeof(struct free_ptr_struct)];
104
  } ptr;
105
} block_header_t;
106
 
107
/* first level index array */
108
typedef struct fl_array_struct {
109
  /* ptr is pointer to next level */
110
  block_header_t **sl_array;
111
  /* n_blocks is the number of the blocks which they are pointed by sl_array */
112
  u32 bitmapSL;
113
} fl_array_t;
114
 
115
/*
116
 * fl_array will be our first level array.
117
 */
118
 
119
static fl_array_t *fl_array;// [MAX_FL_INDEX - MIN_LOG2_SIZE];
120
u32 bitmapFL;
121
/*
122
 * first_bh will be our first memory block allocated by MALLOC function
123
 */
124
static block_header_t *first_bh, *free_block;
125
 
126
static int all_ok = 0;
127
 
128
/*
129
 * header_overhead has size of blocks_header - 2 * ptr to next free block
130
 */
131
static int header_overhead = 0, total_size = 0;
132
 
133
/*
134
 * log2size () returns cell of log2 (len)
135
 * it does a search between MIN_SIZE and MAX_SIZE values
136
 */
137
static int log2size(size_t size, size_t *new_size)
138
{
139
  int i;
140
 
141
  if (size <= 0) {
142
    PRINT_MSG ("ERROR: Chunk length must be > 0\n");
143
    return F_ERROR;
144
  }
145
 
146
 
147
  // MIN_SIZE and MAX_SIZE must be defined  
148
 
149
  if (size <= MIN_SIZE){
150
    *new_size = MIN_SIZE;
151
    return MIN_LOG2_SIZE;
152
  }
153
 
154
  for (i = MIN_LOG2_SIZE;
155
       (i <= MAX_LOG2_SIZE) && (size > (*new_size = (1 << i))) ; i++);
156
 
157
  if (i > MAX_LOG2_SIZE) {
158
    PRINT_MSG ("ERROR: Maximum chunk size exceeded\n");
159
    return F_ERROR;
160
  }
161
 
162
  return i;
163
}
164
 
165
/*
166
 * caculate_reserve () returns the size that has to be reservate for
167
 * avoid fragmentation
168
 */
169
 
170
#define MAX(a, b) (a>b)?a:b
171
 
172
/*
173
  May be calculate_reserve can be improved
174
*/
175
 
176
static inline int calculate_reserve (int size){
177
  //  int internal_frag, dummy;
178
 
179
  //  header_overhead = (int) first_bh -> ptr.buffer - (int) first_bh;  
180
 
181
  //internal_frag = (1 << log2size(size, &dummy)) / MAX_SL_INDEX;
182
 
183
  //dummy = MAX((header_overhead * size / MAX_SL_INDEX) + internal_frag, size);
184
 
185
  return size;//(size + dummy);
186
 
187
}
188
 
189
/*
190
 * mapping_function () returns first and second level index
191
 *
192
 * first level index function is:
193
 * fl = log2 (size)
194
 *
195
 * and second level index function is:
196
 * sl = (size - 2**(log2size (size))) / (log2 (size) - log2 (MAX_SL_INDEX))
197
 *
198
 */
199
static int mapping_function (size_t size, int *fl, int *sl){
200
  int aux;
201
  int new_len;
202
 
203
  // first level = log2 (size)
379 giacomo 204
  *fl = log2size (size, (size_t *)&new_len);
141 trimarchi 205
 
206
  if (new_len == size) {
207
    //  if 2**fl == size, second level must be 0
208
    *sl = 0;
209
  } else {
210
    -- *fl;
211
    aux = *fl - MAX_SL_LOG2_INDEX;
212
    *sl = (int)((size - (new_len >> 1)) >> aux);
213
  }
214
 
215
  *fl -= MIN_LOG2_SIZE;
216
  return F_OK;
217
}
218
 
219
/*
220
 * init_TAD () initialize the structure fl_array to NULL
221
 * and free_block with the initial blocks pointed by ptr
222
 *
223
 * its cost is O (n x m)
224
 */
225
static int init_TAD (size_t size, u8 *ptr){
226
  int n, aux, dummy;
227
  if (!(size > 0)) {
228
    PRINT_MSG ("ERROR: size must be > 0\n");
229
    return F_ERROR;
230
  }
231
  if (MAX_SL_INDEX > MIN_SIZE) {
232
    PRINT_MSG ("ERROR: MAX_SL_INDEX must be < MIN_SIZE\n");
233
    return F_ERROR;
234
  }
235
 
236
  total_size = size;
237
 
379 giacomo 238
  MAX_FL_INDEX = log2size(size, (size_t *)&dummy);
141 trimarchi 239
 
240
  if (MAX_FL_INDEX < 0) return -1;
241
  fl_array = (fl_array_t *) SYSTEM_MALLOC ((MAX_FL_INDEX - MIN_LOG2_SIZE)
242
                                           * sizeof(fl_array_t));
243
  if (fl_array == NULL) return -1;
244
  _init_malloc_ (20);
245
  for (n = 0; n < MAX_FL_INDEX - MIN_LOG2_SIZE; n++) {
246
    fl_array [n].bitmapSL = 0;
247
    aux = (1 << (n + MIN_LOG2_SIZE));
248
    fl_array[n].sl_array = NULL;
249
  }
250
  bitmapFL = 0;
251
 
252
  header_overhead = (int) first_bh -> ptr.buffer - (int) first_bh;
253
  first_bh = (block_header_t *) ptr;
254
 
255
  first_bh -> magic_number = MAGIC_NUMBER;
256
  first_bh -> size = size - header_overhead;
257
  first_bh -> state = BLOCK_FREE;
258
  first_bh -> prev = NULL;
259
  first_bh -> next = NULL;
260
  first_bh -> ptr.free_ptr.prev = NULL;
261
  first_bh -> ptr.free_ptr.next = NULL;
262
 
263
  free_block = first_bh;
264
  //mapping_function (first_bh->size,&n, &m);
265
  //fl_array[n].sl_array[m].ptr= first_bh;
266
  //DIDMA__set_bit (m, fl_array[n].bitmapSL);
267
  //DIDMA__set_bit (n, bitmapFL);
268
  all_ok = 1;
269
  return F_OK;
270
}
271
 
272
/*
273
 * destroy_TAD return a pointer to the initial block
274
 */
275
static void *destroy_TAD (void){
276
  all_ok = 0;
277
  _destroy_malloc_();
278
  return (void *) first_bh;
279
}
280
 
281
/*
282
 * insert_TAD merge a free block pointed by ptr
283
 * with its buddies and then
284
 * insert it into fl_array
285
 *
286
 * The cost of this operation is
287
 * always O (K) = (1)
288
 */
289
static int insert_TAD (u8 *ptr){
290
  int fl, sl;
291
  block_header_t *bh = NULL, *bh2;
292
  int for_free_block = 0;
293
 
294
  if (!all_ok) return F_ERROR;
295
 
296
  bh = (block_header_t *) (ptr - header_overhead);
297
  if (bh -> magic_number != MAGIC_NUMBER)
298
    return F_ERROR;
299
 
300
  THREAD_LOCK();
301
  /*
302
   * now bh is a free block
303
   */
304
  bh -> state = BLOCK_FREE;
305
  bh -> ptr.free_ptr.prev = NULL;
306
  bh -> ptr.free_ptr.next = NULL;
307
 
308
  /*
309
   * first bh will be merge with its free buddies and
310
   * then it will be inserted with the free blocks
311
   */
312
  /*
313
   * it is used to know if bh have to be inserted into free_block or
314
   * into fl_array
315
   */
316
  if (bh -> next == NULL) for_free_block = 1;
317
 
318
  /* is it free the follow block? */
319
  if (bh -> next != NULL) {
320
    bh2 = bh -> next;
321
 
322
    if (bh2 -> magic_number == MAGIC_NUMBER &&
323
        bh2 -> state == BLOCK_FREE) {
324
      /* we are lucky, we can merge bh with the next block */
325
 
326
      if (bh2 == free_block) for_free_block = 1;
327
      bh2 -> magic_number = MAGIC_NUMBER_NONE;
328
      if (bh2 -> next != NULL)
329
        bh2 -> next -> prev = bh;
330
      if (!for_free_block) {
331
        if (bh2 -> ptr.free_ptr.next != NULL)
332
          bh2 -> ptr.free_ptr.next -> ptr.free_ptr.prev =
333
            bh2  -> ptr.free_ptr.prev;
334
 
335
        if (bh2 -> ptr.free_ptr.prev != NULL)
336
          bh2 -> ptr.free_ptr.prev -> ptr.free_ptr.next =
337
            bh2 -> ptr.free_ptr.next;
338
        //mapping_function (bh2 -> size, &fl, &sl);
339
        fl = bh2 -> ptr.free_ptr.first_l_index;
340
        sl = bh2 -> ptr.free_ptr.second_l_index;
341
        /* bh2 must be erased from fl_array */
342
        if (fl_array [fl].sl_array [sl] == bh2)
343
          fl_array [fl].sl_array [sl] = bh2 -> ptr.free_ptr.next;
344
 
345
          //fl_array [fl].n_blocks --;
346
          if (fl_array [fl].sl_array [sl] == NULL){
347
            //fl_array[fl].bitmapSL &= ~(1 << sl);
348
            DIDMA__clear_bit (sl, fl_array[fl].bitmapSL);
349
            if (!fl_array[fl].bitmapSL) {
350
              _free_ ((void *) fl_array [fl].sl_array);
351
              DIDMA__clear_bit (fl, bitmapFL);
352
            }
353
          }
354
      }
355
      bh -> size += bh2 -> size + header_overhead;
356
      bh -> next = bh2 -> next;
357
    }
358
  }
359
 
360
  /* is it free the previous block? */
361
  if (bh -> prev != NULL) {
362
    bh2 = bh -> prev;
363
    if (bh2 -> magic_number == MAGIC_NUMBER &&
364
      bh2 -> state == BLOCK_FREE) {
365
      bh -> magic_number = MAGIC_NUMBER_NONE;
366
 
367
      if (bh -> next != NULL)
368
        bh -> next -> prev = bh2;
369
 
370
      if (bh2 -> ptr.free_ptr.next != NULL)
371
        bh2 -> ptr.free_ptr.next -> ptr.free_ptr.prev =
372
          bh2  -> ptr.free_ptr.prev;
373
 
374
      if (bh2 -> ptr.free_ptr.prev != NULL)
375
        bh2 -> ptr.free_ptr.prev -> ptr.free_ptr.next =
376
          bh2 -> ptr.free_ptr.next;
377
 
378
      //mapping_function (bh2 -> size, &fl, &sl);
379
 
380
      fl = bh2 -> ptr.free_ptr.first_l_index;
381
      sl = bh2 -> ptr.free_ptr.second_l_index;
382
      if (fl_array [fl].sl_array [sl] == bh2)
383
        fl_array [fl].sl_array [sl] = bh2 -> ptr.free_ptr.next;
384
 
385
      if (fl_array[fl].sl_array[sl] == NULL){
386
        //fl_array[fl].bitmapSL &= ~(1 << sl);
387
        DIDMA__clear_bit (sl, fl_array[fl].bitmapSL);
388
        if (!fl_array[fl].bitmapSL) {
389
          _free_ ((void *) fl_array [fl].sl_array);
390
          DIDMA__clear_bit (fl, bitmapFL);
391
        }
392
      }
393
 
394
      bh2 -> size += bh -> size + header_overhead;
395
      bh2 -> next = bh -> next;
396
      bh = bh2;
397
 
398
    }
399
  }
400
 
401
  /*
402
   * and then we merge the free block with the initial memory
403
   */
404
    if (for_free_block) {
405
      free_block = bh;
406
      bh -> ptr.free_ptr.next = NULL;
407
      bh -> ptr.free_ptr.prev = NULL;
408
    } else {
409
      /*
410
       * or we insert the free block in the TAD
411
       */
412
      mapping_function (bh -> size, &fl, &sl);
413
      if (fl_array[fl].bitmapSL == 0)
414
        fl_array[fl].sl_array = (block_header_t **) _malloc_ ();
415
      if (fl_array[fl].sl_array == NULL) {
416
        PRINT_MSG("CRITICAL ERROR: there isn't enought memory for free\n");
229 giacomo 417
        THREAD_UNLOCK();
418
        return F_ERROR;
141 trimarchi 419
      }
420
      bh -> ptr.free_ptr.first_l_index = fl;
421
      bh -> ptr.free_ptr.second_l_index = sl;
422
      bh -> ptr.free_ptr.next = fl_array [fl].sl_array [sl];
423
      bh -> ptr.free_ptr.prev = NULL;
424
      if (fl_array [fl].sl_array [sl] != NULL)
425
        fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = bh;
426
      fl_array [fl].sl_array [sl] = bh;
427
 
428
      DIDMA__set_bit (sl, fl_array[fl].bitmapSL);
429
      DIDMA__set_bit (fl, bitmapFL);
430
 
431
    }
432
 
433
  THREAD_UNLOCK();
434
  return F_OK;
435
}
436
 
437
/*
438
 * search_TAD searchs a free block of size 'size'
439
 * then this block will be splitted in two new blocks,
440
 * one of these new blocks will be given to the user and the
441
 * other will be inserted into a free blocks structure
442
 *
443
 * The cost of this operation is
444
 *      best case: (K) = (1)  
445
 *      worst case: (MAX_FL_LOG2_INDEX - MIN_FL_LOG2_INDEX + MAX_SL_INDEX + K)
446
 *                   = (1)
447
 * where K is an integer constant
448
 */
449
 
450
static u8 *search_TAD (size_t size) {
451
  int for_free_block = 0;
452
  int fl, sl, n;
453
  int found;
454
  block_header_t *bh = NULL, *bh2;
455
 
456
  if (!(size > 0) || size >= MAX_SIZE || !all_ok) return NULL;
457
  THREAD_LOCK();
458
 
459
  if (size <= MIN_SIZE) {
460
    size = MIN_SIZE;
461
    fl = 0;
462
    sl = 0;
463
  } else {
464
    mapping_function (size, &fl, &sl);
465
 
466
    if (++sl == MAX_SL_INDEX) {
467
      fl ++;
468
      sl = 0;
469
    }
470
    /*
471
     * This is the reason of the internal fragmentation
472
     * The block given is greater that the size demanded
473
     */
474
    size = (1 << (fl + MIN_LOG2_SIZE));
475
    size = size + ((size >> MAX_SL_LOG2_INDEX) * sl);
476
  }
477
 
478
  /* the size given can be bigger than the size demanded */
479
  found = 0;
480
 
481
  // we take the first free block from fl_array or a buddy of him
482
 
483
  sl = fl_array[fl].bitmapSL & ((~0) << sl);
484
  if (sl != 0) {
485
    sl = DIDMA_fls(sl);
486
    bh = fl_array [fl].sl_array [sl];
487
    fl_array [fl].sl_array [sl] = bh -> ptr.free_ptr.next;
488
    if (fl_array [fl].sl_array [sl] != NULL)
489
      fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = NULL;
490
    else {
491
      DIDMA__clear_bit (sl, fl_array[fl].bitmapSL);
492
      if (!fl_array[fl].bitmapSL) {
493
        DIDMA__clear_bit (fl, bitmapFL);
494
        _free_ ((void *) fl_array [fl].sl_array);
495
      }
496
    }
497
    found = 1;
498
    goto out;
499
  }
500
  /*
501
   * if fl_array is empty we will take a free block
502
   * from free_block pointer
503
   */
504
 
505
  if (free_block != NULL && free_block -> size >= size) {
506
    bh = free_block;
507
    free_block = NULL;
508
    for_free_block = 1;
509
    found = 1;
510
    goto out;
511
  }
512
 
513
  /*
514
   * A free block is searched
515
   *
516
   * Using a bitmap
517
   */
518
 
519
  fl = DIDMA_fls(bitmapFL & ((~0) << (fl + 1)));
520
 
521
  if (fl > 0) {
522
    sl = DIDMA_fls(fl_array[fl].bitmapSL);
523
    bh = fl_array [fl].sl_array [sl];
524
    fl_array [fl].sl_array [sl] = bh -> ptr.free_ptr.next;
525
    if (fl_array [fl].sl_array [sl] != NULL){
526
      fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = NULL;
527
    } else {
528
      DIDMA__clear_bit (sl, fl_array[fl].bitmapSL);
529
      if (!fl_array[fl].bitmapSL) {
530
        _free_ ((void *) fl_array[fl].sl_array);
531
        DIDMA__clear_bit (fl, bitmapFL);
532
      }
533
    }
534
    found = 1;
535
    goto out;
536
  }
537
 
538
 out:
539
 
540
  /*
541
   * HUGGGG, NOT ENOUGHT MEMORY
542
   * I think that we have done all that we have been able
543
   */
544
  if (!found) {
545
    PRINT_MSG ("ERROR: Memory pool exhausted!!!\n");
546
    THREAD_UNLOCK();
547
    return NULL;
548
  }
549
 
550
  /*
551
   * we can say: YESSSSSSSSSSS, we have enought memory!!!!
552
   */
553
  bh -> state = BLOCK_USED;
554
 
555
  /* can bh be splitted? */
556
  n = (int)(bh -> size - size - header_overhead);
557
  if (n >= (int) MIN_SIZE) {
558
 
559
    /*
560
     * Yes, bh will be splitted
561
     */
562
 
563
    bh2 = (block_header_t *) ((u8 *)(bh -> ptr.buffer) + size);    
564
    bh2 -> magic_number = MAGIC_NUMBER;
565
    bh2 -> state = BLOCK_FREE;
566
    bh2 -> size = n;
567
    if (bh -> next != NULL)
568
      bh -> next -> prev = bh2;
569
    bh2 -> next = bh -> next;
570
    bh -> next = bh2;
571
    bh2 -> prev = bh;
572
    bh -> size = size;
573
 
574
    if (!for_free_block) {
575
      mapping_function (bh2 -> size, &fl, &sl);
576
      if (fl_array[fl].bitmapSL == 0)
577
        fl_array[fl].sl_array = (block_header_t **) _malloc_ ();
578
      if (fl_array[fl].sl_array == NULL) {
579
        PRINT_MSG("CRITICAL ERROR: there isn't enought memory for free\n");
580
        return NULL;
581
      }
582
      bh2 -> ptr.free_ptr.first_l_index = fl;
583
      bh2 -> ptr.free_ptr.second_l_index = sl;
584
      bh2 -> ptr.free_ptr.prev = NULL;
585
      bh2 -> ptr.free_ptr.next = fl_array [fl].sl_array [sl];
586
 
587
      if (fl_array [fl].sl_array [sl] != NULL)
588
        fl_array [fl].sl_array [sl] -> ptr.free_ptr.prev = bh2;
589
      fl_array [fl].sl_array [sl] = bh2;
590
      DIDMA__set_bit (sl, fl_array[fl].bitmapSL);
591
      DIDMA__set_bit (fl, bitmapFL);
592
 
593
        //fl_array [fl].n_blocks ++;
594
    } else
595
      free_block = bh2;
596
  }
597
  THREAD_UNLOCK();
598
  return (u8 *) bh -> ptr.buffer;
599
}
600
 
601
 
602
int init_memory_pool (int max_size){
603
 
604
  u8 *buffer;
605
  int real_max_size = 0;
606
 
607
  if (max_size < 0) return -1;
608
 
609
 
610
  //buffer = (u8 *) SYSTEM_MALLOC (real_max_size * sizeof (u8));
611
  real_max_size = calculate_reserve(max_size);
612
  buffer = (u8 *) SYSTEM_MALLOC (real_max_size * sizeof (u8));
613
  if (buffer == NULL) return F_ERROR;
614
  return init_TAD (real_max_size, buffer);
615
}
616
 
617
void destroy_memory_pool(void){
618
 
619
        SYSTEM_FREE (destroy_TAD ());
620
}
621
 
622
/* see 'man malloc' */
623
void *rt_malloc (size_t size){
624
  return (void *) search_TAD (size);
625
}
626
 
627
/* see 'man free' */
628
void rt_free (void *ptr){
629
  if (ptr != NULL) insert_TAD ((u8 *) ptr);
630
}
631
 
632
/* see 'man calloc' */
633
void *rt_calloc (size_t nelem, size_t elem_size)
634
{
635
  void *p;
636
 
637
  if (!all_ok || nelem <= 0 || elem_size <= 0) return NULL;
638
 
639
  if ((p = rt_malloc (nelem * elem_size)) == NULL)
640
    return NULL;
641
 
642
  memset (p, 0, nelem * elem_size);
643
 
644
  return p;
645
}
646
 
647
/*
648
 * see man realloc  
649
 * be careful, realloc () is an expensive operation because
650
 * it uses malloc () and free ()
651
 */
652
void *rt_realloc (void *p, size_t new_len)
653
{
654
  u8 *aux;
655
  void *addr;
656
  int old_len, min;
657
  block_header_t *b;
658
 
659
  if (!all_ok) return NULL;
660
 
661
  if (p == NULL)
662
    return rt_malloc (new_len);
663
  else if (new_len == 0) {
664
    rt_free(p);
665
    return NULL;
666
  } else {
667
    /*
668
     * Now we try to achieve old size because
669
     * then we need it to copy all data in the new allocated
670
     * memory
671
     */
672
    aux = (u8 *) p;
673
    aux -= header_overhead;
674
    b = (block_header_t *) aux;
675
    if (b -> magic_number == MAGIC_NUMBER) {
676
      old_len = b -> size;
677
    } else {
678
      PRINT_MSG ("CRITICAL ERROR: block corrupted\n");
679
      return NULL;
680
    }
681
 
682
    addr = rt_malloc (new_len);
683
 
684
    if (addr == NULL) return NULL;
685
 
686
    min = (old_len > new_len)? new_len : old_len;
687
    memcpy (addr, p, min);
688
    rt_free (p);
689
 
690
    return addr;
691
  }
692
}
693
 
694
#ifdef __DEBUG__
695
 
696
/*
697
 * dump_mem () is a simple operation,
698
 * it only does a dumped of memory
699
 */
700
 
701
void dump_mem (void){
702
  u8 *aux;
703
  int n;
704
 
705
  if (!all_ok) return;
706
 
707
  aux = (u8 *) first_bh;
708
 
709
  for (n = 0; n < total_size; n++) {
710
    PRINT_DBG_H (aux [n]);
711
    PRINT_DBG_C (" ");
712
  }
713
  PRINT_DBG_C ("\n");
714
}
715
 
716
/*
717
 * I haven't anything to say about print_block ()
718
 */
719
static void print_block (block_header_t *b){
720
  if (b == NULL) return;
721
  PRINT_DBG_C (">>>> MNum 0x");
722
  PRINT_DBG_H (b -> magic_number);
723
  PRINT_DBG_C (" Address 0x");
724
  //PRINT_DBG_H (b);
725
  if (b -> state == BLOCK_FREE)
726
    PRINT_DBG_C (" State FREE");
727
  else
728
    PRINT_DBG_C (" State USED");
729
  PRINT_DBG_C (" Size ");
730
  PRINT_DBG_D (b -> size);
731
  PRINT_DBG_C ("\n---- Prev 0x");
732
  //PRINT_DBG_H (b -> prev);
733
  PRINT_DBG_C (" Next 0x");
734
  //PRINT_DBG_H (b -> next);
735
  if (b -> state == BLOCK_FREE){
736
    PRINT_DBG_C ("\n---- Prev Free 0x");
737
    //PRINT_DBG_H (b -> ptr.free_ptr.prev);
738
    PRINT_DBG_C (" Next Free 0x");
739
    //PRINT_DBG_H (b -> ptr.free_ptr.next);
740
  }
741
  PRINT_DBG_C ("\n");
742
}
743
 
744
/*
745
 * structure_context () show the content of all blocks
746
 */
747
void structure_context (void) {
748
  block_header_t *b;
749
 
750
  if (!all_ok) return;
751
 
752
  b = first_bh;
753
  PRINT_DBG_C ("\nALL BLOCKS\n");
754
  while (b != NULL) {
755
    print_block (b);
756
    b = b -> next;
757
  }
758
 
759
}
760
 
761
/*
762
 * global_state () returns overhead, free and used space
763
 */
764
void global_state (int *free, int *used, int *overhead){
765
  block_header_t *b;
766
 
767
  *free = 0;
768
  *used = 0;
769
  *overhead = 0;
770
  if (!all_ok) return;
771
  b = first_bh;
772
  while (b != NULL) {
773
    if (b -> state == BLOCK_USED) {
774
      *used += b -> size;
775
    } else {
776
      *free += b -> size;
777
    }
778
    b = b -> next;
779
    *overhead += header_overhead;
780
  }
781
 
782
}
783
 
784
/*
785
 * free_blocks_context () show the content
786
 * of free blocks
787
 */
788
void free_blocks_context (void){
789
  int i, j;
790
  block_header_t *b;
791
 
792
  if (!all_ok) return;
793
 
794
  PRINT_DBG_C ("\nFREE BLOCKS\n");
795
  PRINT_DBG_C ("MAIN BLOCK\n");
796
  print_block (free_block);
797
  PRINT_DBG_C ("FRAGMENTED BLOCKS\n");
798
  for (i = MAX_FL_INDEX - 1 - MIN_LOG2_SIZE; i >= 0; i--) {
799
    if (fl_array [i].bitmapSL > 0)
800
      for (j = MAX_SL_INDEX - 1; j >= 0; j--) {
801
        if (fl_array [i].sl_array[j] != NULL) {
802
          b = fl_array [i].sl_array [j];
803
          PRINT_DBG_C ("[");
804
          PRINT_DBG_D (i);
805
          PRINT_DBG_C ("] ");
806
          PRINT_DBG_D (1 << (i + MIN_LOG2_SIZE));
807
          PRINT_DBG_C (" bytes -> Free blocks: 0x");
808
          PRINT_DBG_H (fl_array [i].bitmapSL);
809
          PRINT_DBG_C ("\n");
810
 
811
          while (b != NULL) {
812
            PRINT_DBG_C (">>>> ");
813
            PRINT_DBG_D ((1 << (i + MIN_LOG2_SIZE)) +
814
                         (1<< (i + MIN_LOG2_SIZE)) / MAX_SL_INDEX * j);
815
            PRINT_DBG_C (" bytes\n");
816
            print_block (b);
817
            b = b -> ptr.free_ptr.next;
818
          }
819
        }
820
      }
821
  }
822
}
823
 
824
/*
825
 * check_mem () checks memory searching
826
 * errors and incoherences
827
 * return :
828
 * 0 if there isn't any error
829
 * or
830
 * -1 in other case
831
 */
832
int check_mem (void){
833
  block_header_t *b, *b2;
834
  int i, j, num_blocks;
835
 
836
  if (!all_ok) return F_ERROR;
837
 
838
  b = first_bh;
839
  num_blocks = 0;
840
  for (i = MAX_FL_INDEX - 1 - MIN_LOG2_SIZE; i >= 0; i--) {
841
    if (fl_array [i].bitmapSL < 0) return F_ERROR;
842
    for (j = MAX_SL_INDEX - 1; j >= 0; j--) {
843
      b2 = fl_array [i].sl_array[j];
844
      while (b2 != NULL) {
845
        b2 = b2 -> ptr.free_ptr.next;
846
        num_blocks ++;
847
      }
848
    }
849
    if (num_blocks != fl_array [i].bitmapSL) return F_ERROR;
850
    num_blocks = 0;
851
  }
852
 
853
  while (b != NULL) {
854
    if (b -> magic_number != MAGIC_NUMBER ||
855
        b -> size > MAX_SIZE || b -> size < MIN_SIZE)
856
      return F_ERROR;
857
 
858
    if (b -> next != NULL)
859
      if (b -> next < first_bh || b -> next >
860
          (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE))
861
        return F_ERROR;
862
 
863
    if (b -> prev != NULL)
864
      if (b -> prev < first_bh || b -> prev >
865
          (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE) )
866
        return F_ERROR;
867
 
868
    if (b -> state != BLOCK_FREE && b -> state != BLOCK_USED) return F_ERROR;
869
    if (b -> state == BLOCK_FREE) {
870
      if (b -> ptr.free_ptr.next != NULL)
871
        if (b -> ptr.free_ptr.next < first_bh ||
872
            b -> ptr.free_ptr.next >
873
            (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE))
874
          return F_ERROR;
875
 
876
      if (b -> ptr.free_ptr.prev != NULL)
877
        if (b -> ptr.free_ptr.prev < first_bh ||
878
            b -> ptr.free_ptr.prev >
879
            (block_header_t *) ((u8 *) (first_bh) + MAX_SIZE) )
880
            return F_ERROR;
881
    }
882
 
883
    b = b -> next;
884
 
885
  }
886
  return F_OK;
887
}
888
#endif // #ifdef __DEBUG__