sys/i386/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  */
  32
  33 /*
  34  * Simple memory allocator for the bootstrap loader.  Probably suffers
  35  * a lot from fragmentation.
  36  */
  37
  38 #include "boot.h"
  39
  40 #include <stddef.h>
  41
  42 /* ``Nobody will ever need more than 640 KB of RAM.'' :-) */
  43 #define MAXBRK (640 * 1024 * 1024)
  44
  45 /* allocation unit */
  46 #define NCHUNKS 2048
  47
  48 struct chunk
  49 {
  50         struct chunk *next;
  51         size_t len;
  52 };
  53
  54 static void *brkval;
  55 static struct chunk *freelist;
  56
  57 void *
  58 malloc(size_t len)
  59 {
  60         struct chunk *p, *q, *oldp;
  61         size_t nelems;
  62
  63         nelems = (len + sizeof(struct chunk) - 1) / sizeof(struct chunk) + 1;
  64
  65         /*
  66          * First, see if we can satisfy the request from the freelist.
  67          */
  68         for (p = freelist, oldp = 0;
  69              p && p != (struct chunk *)brkval;
  70              oldp = p, p = p->next) {
  71                 if (p->len > nelems) {
  72                         /* chunk is larger, shorten, and return the tail */
  73                         p->len -= nelems;
  74                         q = p + p->len;
  75                         q->next = 0;
  76                         q->len = nelems;
  77                         q++;
  78                         return (void *)q;
  79                 }
  80                 if (p->len == nelems) {
  81                         /* exact match, remove from freelist */
  82                         if (oldp == 0)
  83                                 freelist = p->next;
  84                         else
  85                                 oldp->next = p->next;
  86                         p->next = 0;
  87                         p++;
  88                         return (void *)p;
  89                 }
  90         }
  91         /*
  92          * Nothing found on freelist, try obtaining more space.
  93          */
  94         if (brkval == 0)
  95                 brkval = &end;
  96         q = p = (struct chunk *)brkval;
  97         if ((int)(p + NCHUNKS) > MAXBRK)
  98                 return 0;
  99
 100         p += NCHUNKS;
 101         brkval = p;
 102
 103         q->next = p;
 104         q->len = NCHUNKS;
 105
 106         if (oldp == 0)
 107                 freelist = q;
 108         else {
 109                 if (oldp + oldp->len == q) {
 110                         /* extend last chunk */
 111                         oldp->len += NCHUNKS;
 112                         oldp->next = p;
 113                 } else
 114                         oldp->next = q;
 115         }
 116
 117         return malloc(len);
 118 }
 119
 120 void
 121 free(void *ptr)
 122 {
 123         struct chunk *p, *q, *oldp;
 124
 125         if (ptr == 0)
 126                 return;
 127
 128         q = (struct chunk *)ptr;
 129         q--;
 130         if (q->next != 0) {
 131                 printf("malloc error: botched ptr to free()\n");
 132                 return;
 133         }
 134
 135         /*
 136          * Walk the freelist, and insert in the correct sequence.
 137          */
 138         for (p = freelist, oldp = 0;
 139              p && p != (struct chunk *)brkval;
 140              oldp = p, p = p->next) {
 141                 if ((unsigned)p > (unsigned)q) {
 142                         if (q + q->len == p) {
 143                                 /* aggregate with next chunk */
 144                                 q->len += p->len;
 145                                 q->next = p->next;
 146                                 p = p->next;
 147                         }
 148                         if (oldp) {
 149                                 if (oldp + oldp->len == q) {
 150                                 /* aggregate with previous chunk */
 151                                         oldp->len += q->len;
 152                                         oldp->next = p;
 153                                 } else {
 154                                 /* insert into chain */
 155                                         q->next = p;
 156                                         oldp->next = q;
 157                                 }
 158                                 return;
 159                         }
 160                         q->next = p;
 161                         freelist = q;
 162                 }
 163         }
 164         if (oldp) {
 165                 /* we are topmost */
 166                 if (oldp + oldp->len == q) {
 167                         /* aggregate with previous chunk */
 168                         oldp->len += q->len;
 169                         oldp->next = p;
 170                 } else {
 171                         oldp->next = q;
 172                         q->next = p;
 173                 }
 174                 return;
 175         }
 176         /* we are alone on the freelist */
 177         freelist = q;
 178 }
 179