sys/platform/pc32/boot/cdboot/malloc.c

   1 /*
   2  * Copyright © 1997 Pluto Technologies International, Inc.  Boulder CO
   3  * Copyright © 1997 interface business GmbH, Dresden.
   4  *      All rights reserved.
   5  *
   6  * This code was written by Jörg Wunsch, Dresden.
   7  * Direct comments to <joerg_wunsch@interface-business.de>.
   8  *
   9  * Redistribution and use in source and binary forms, with or without
  10  * modification, are permitted provided that the following conditions
  11  * are met:
  12  * 1. Redistributions of source code must retain the above copyright
  13  *    notice, this list of conditions and the following disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR(S) ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  20  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  21  * DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT,
  22  * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  23  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  24  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  25  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  26  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
  27  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  28  * POSSIBILITY OF SUCH DAMAGE.
  29  *
  30  * $FreeBSD: src/sys/i386/boot/cdboot/malloc.c,v 1.2 1999/08/28 00:43:18 peter Exp $
  31  * $DragonFly: src/sys/platform/pc32/boot/cdboot/Attic/malloc.c,v 1.2 2003/06/17 04:28:34 dillon Exp $
  32  */
  33
  34 /*
  35  * Simple memory allocator for the bootstrap loader.  Probably suffers
  36  * a lot from fragmentation.
  37  */
  38
  39 #include "boot.h"
  40
  41 #include <stddef.h>
  42
  43 /* ``Nobody will ever need more than 640 KB of RAM.'' :-) */
  44 #define MAXBRK (640 * 1024 * 1024)
  45
  46 /* allocation unit */
  47 #define NCHUNKS 2048
  48
  49 struct chunk
  50 {
  51         struct chunk *next;
  52         size_t len;
  53 };
  54
  55 static void *brkval;
  56 static struct chunk *freelist;
  57
  58 void *
  59 malloc(size_t len)
  60 {
  61         struct chunk *p, *q, *oldp;
  62         size_t nelems;
  63
  64         nelems = (len + sizeof(struct chunk) - 1) / sizeof(struct chunk) + 1;
  65
  66         /*
  67          * First, see if we can satisfy the request from the freelist.
  68          */
  69         for (p = freelist, oldp = 0;
  70              p && p != (struct chunk *)brkval;
  71              oldp = p, p = p->next) {
  72                 if (p->len > nelems) {
  73                         /* chunk is larger, shorten, and return the tail */
  74                         p->len -= nelems;
  75                         q = p + p->len;
  76                         q->next = 0;
  77                         q->len = nelems;
  78                         q++;
  79                         return (void *)q;
  80                 }
  81                 if (p->len == nelems) {
  82                         /* exact match, remove from freelist */
  83                         if (oldp == 0)
  84                                 freelist = p->next;
  85                         else
  86                                 oldp->next = p->next;
  87                         p->next = 0;
  88                         p++;
  89                         return (void *)p;
  90                 }
  91         }
  92         /*
  93          * Nothing found on freelist, try obtaining more space.
  94          */
  95         if (brkval == 0)
  96                 brkval = &end;
  97         q = p = (struct chunk *)brkval;
  98         if ((int)(p + NCHUNKS) > MAXBRK)
  99                 return 0;
 100
 101         p += NCHUNKS;
 102         brkval = p;
 103
 104         q->next = p;
 105         q->len = NCHUNKS;
 106
 107         if (oldp == 0)
 108                 freelist = q;
 109         else {
 110                 if (oldp + oldp->len == q) {
 111                         /* extend last chunk */
 112                         oldp->len += NCHUNKS;
 113                         oldp->next = p;
 114                 } else
 115                         oldp->next = q;
 116         }
 117
 118         return malloc(len);
 119 }
 120
 121 void
 122 free(void *ptr)
 123 {
 124         struct chunk *p, *q, *oldp;
 125
 126         if (ptr == 0)
 127                 return;
 128
 129         q = (struct chunk *)ptr;
 130         q--;
 131         if (q->next != 0) {
 132                 printf("malloc error: botched ptr to free()\n");
 133                 return;
 134         }
 135
 136         /*
 137          * Walk the freelist, and insert in the correct sequence.
 138          */
 139         for (p = freelist, oldp = 0;
 140              p && p != (struct chunk *)brkval;
 141              oldp = p, p = p->next) {
 142                 if ((unsigned)p > (unsigned)q) {
 143                         if (q + q->len == p) {
 144                                 /* aggregate with next chunk */
 145                                 q->len += p->len;
 146                                 q->next = p->next;
 147                                 p = p->next;
 148                         }
 149                         if (oldp) {
 150                                 if (oldp + oldp->len == q) {
 151                                 /* aggregate with previous chunk */
 152                                         oldp->len += q->len;
 153                                         oldp->next = p;
 154                                 } else {
 155                                 /* insert into chain */
 156                                         q->next = p;
 157                                         oldp->next = q;
 158                                 }
 159                                 return;
 160                         }
 161                         q->next = p;
 162                         freelist = q;
 163                 }
 164         }
 165         if (oldp) {
 166                 /* we are topmost */
 167                 if (oldp + oldp->len == q) {
 168                         /* aggregate with previous chunk */
 169                         oldp->len += q->len;
 170                         oldp->next = p;
 171                 } else {
 172                         oldp->next = q;
 173                         q->next = p;
 174                 }
 175                 return;
 176         }
 177         /* we are alone on the freelist */
 178         freelist = q;
 179 }
 180