Annotation of sys/arch/sparc64/stand/ofwboot/alloc.c, Revision 1.1
1.1 ! nbrk 1: /* $OpenBSD: alloc.c,v 1.4 2007/05/28 22:17:21 pyr Exp $ */
! 2: /* $NetBSD: alloc.c,v 1.1 2000/08/20 14:58:37 mrg Exp $ */
! 3:
! 4: /*
! 5: * Copyright (c) 1997 Jason R. Thorpe. All rights reserved.
! 6: * Copyright (c) 1997 Christopher G. Demetriou. All rights reserved.
! 7: * Copyright (c) 1996
! 8: * Matthias Drochner. All rights reserved.
! 9: * Copyright (C) 1995, 1996 Wolfgang Solfrank.
! 10: * Copyright (C) 1995, 1996 TooLs GmbH.
! 11: * All rights reserved.
! 12: *
! 13: * Redistribution and use in source and binary forms, with or without
! 14: * modification, are permitted provided that the following conditions
! 15: * are met:
! 16: * 1. Redistributions of source code must retain the above copyright
! 17: * notice, this list of conditions and the following disclaimer.
! 18: * 2. Redistributions in binary form must reproduce the above copyright
! 19: * notice, this list of conditions and the following disclaimer in the
! 20: * documentation and/or other materials provided with the distribution.
! 21: * 3. All advertising materials mentioning features or use of this software
! 22: * must display the following acknowledgement:
! 23: * This product includes software developed by TooLs GmbH.
! 24: * 4. The name of TooLs GmbH may not be used to endorse or promote products
! 25: * derived from this software without specific prior written permission.
! 26: *
! 27: * THIS SOFTWARE IS PROVIDED BY TOOLS GMBH ``AS IS'' AND ANY EXPRESS OR
! 28: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
! 29: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
! 30: * IN NO EVENT SHALL TOOLS GMBH BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
! 31: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
! 32: * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
! 33: * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
! 34: * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
! 35: * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
! 36: * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
! 37: */
! 38:
! 39: /*
! 40: * Dynamic memory allocator suitable for use with OpenFirmware.
! 41: *
! 42: * Compile options:
! 43: *
! 44: * ALLOC_TRACE enable tracing of allocations/deallocations
! 45: *
! 46: * ALLOC_FIRST_FIT use a first-fit allocation algorithm, rather than
! 47: * the default best-fit algorithm.
! 48: *
! 49: * DEBUG enable debugging sanity checks.
! 50: */
! 51:
! 52: #include <sys/param.h>
! 53: #include <sys/queue.h>
! 54:
! 55: #include <lib/libsa/stand.h>
! 56:
! 57: #include "openfirm.h"
! 58:
! 59: /*
! 60: * Each block actually has ALIGN(struct ml) + ALIGN(size) bytes allocated
! 61: * to it, as follows:
! 62: *
! 63: * 0 ... (sizeof(struct ml) - 1)
! 64: * allocated or unallocated: holds size of user-data part of block.
! 65: *
! 66: * sizeof(struct ml) ... (ALIGN(sizeof(struct ml)) - 1)
! 67: * allocated: unused
! 68: * unallocated: depends on packing of struct fl
! 69: *
! 70: * ALIGN(sizeof(struct ml)) ... (ALIGN(sizeof(struct ml)) +
! 71: * ALIGN(data size) - 1)
! 72: * allocated: user data
! 73: * unallocated: depends on packing of struct fl
! 74: *
! 75: * 'next' is only used when the block is unallocated (i.e. on the free list).
! 76: * However, note that ALIGN(sizeof(struct ml)) + ALIGN(data size) must
! 77: * be at least 'sizeof(struct fl)', so that blocks can be used as structures
! 78: * when on the free list.
! 79: */
! 80:
! 81: /*
! 82: * Memory lists.
! 83: */
! 84: struct ml {
! 85: unsigned size;
! 86: LIST_ENTRY(ml) list;
! 87: };
! 88:
! 89: LIST_HEAD(, ml) freelist = LIST_HEAD_INITIALIZER(freelist);
! 90: LIST_HEAD(, ml) allocatedlist = LIST_HEAD_INITIALIZER(allocatedlist);
! 91:
! 92: #define OVERHEAD ALIGN(sizeof (struct ml)) /* shorthand */
! 93:
! 94: void *
! 95: alloc(size)
! 96: unsigned size;
! 97: {
! 98: struct ml *f, *bestf;
! 99: unsigned bestsize = 0xffffffff; /* greater than any real size */
! 100: char *help;
! 101: int failed;
! 102:
! 103: #ifdef ALLOC_TRACE
! 104: printf("alloc(%u)", size);
! 105: #endif
! 106:
! 107: /*
! 108: * Account for overhead now, so that we don't get an
! 109: * "exact fit" which doesn't have enough space.
! 110: */
! 111: size = ALIGN(size) + OVERHEAD;
! 112:
! 113: #ifdef ALLOC_FIRST_FIT
! 114: /* scan freelist */
! 115: LIST_FOREACH(f, &freelist, list)
! 116: if (f->size >= size)
! 117: break;
! 118: bestf = f;
! 119: failed = (bestf == (struct fl *)0);
! 120: #else
! 121: /* scan freelist */
! 122: LIST_FOREACH(f, &freelist, list) {
! 123: if (f->size >= size) {
! 124: if (f->size == size) /* exact match */
! 125: goto found;
! 126:
! 127: if (f->size < bestsize) {
! 128: /* keep best fit */
! 129: bestf = f;
! 130: bestsize = f->size;
! 131: }
! 132: }
! 133: }
! 134:
! 135: /* no match in freelist if bestsize unchanged */
! 136: failed = (bestsize == 0xffffffff);
! 137: #endif
! 138:
! 139: if (failed) { /* nothing found */
! 140: /*
! 141: * Allocate memory from the OpenFirmware, rounded
! 142: * to page size, and record the chunk size.
! 143: */
! 144: size = roundup(size, NBPG);
! 145: help = OF_claim(0, size, NBPG);
! 146: if (help == (char *)-1)
! 147: panic("alloc: out of memory");
! 148:
! 149: f = (struct ml *)help;
! 150: f->size = size;
! 151: #ifdef ALLOC_TRACE
! 152: printf("=%lx (new chunk size %u)\n",
! 153: (u_long)(help + OVERHEAD), f->size);
! 154: #endif
! 155: goto out;
! 156: }
! 157:
! 158: /* we take the best fit */
! 159: f = bestf;
! 160:
! 161: found:
! 162: /* remove from freelist */
! 163: LIST_REMOVE(f, list);
! 164: help = (char *)f;
! 165: #ifdef ALLOC_TRACE
! 166: printf("=%lx (origsize %u)\n", (u_long)(help + OVERHEAD), f->size);
! 167: #endif
! 168: out:
! 169: /* place on allocated list */
! 170: LIST_INSERT_HEAD(&allocatedlist, f, list);
! 171: return (help + OVERHEAD);
! 172: }
! 173:
! 174: void
! 175: free(ptr, size)
! 176: void *ptr;
! 177: unsigned size; /* only for consistenct check */
! 178: {
! 179: register struct ml *a = (struct ml *)((char *)ptr - OVERHEAD);
! 180:
! 181: #ifdef ALLOC_TRACE
! 182: printf("free(%lx, %u) (origsize %u)\n", (u_long)ptr, size, a->size);
! 183: #endif
! 184: #ifdef DEBUG
! 185: if (size > a->size)
! 186: printf("free %u bytes @%lx, should be <=%u\n",
! 187: size, (u_long)ptr, a->size);
! 188: #endif
! 189:
! 190: /* Remove from allocated list, place on freelist. */
! 191: LIST_REMOVE(a, list);
! 192: LIST_INSERT_HEAD(&freelist, a, list);
! 193: }
! 194:
! 195: void
! 196: freeall()
! 197: {
! 198: #ifdef __notyet__ /* Firmware bug ?! */
! 199: struct ml *m;
! 200:
! 201: /* Release chunks on freelist... */
! 202: while ((m = TAILQ_FIRST(&freelist)) != NULL)) {
! 203: LIST_REMOVE(m, list);
! 204: OF_release(m, m->size);
! 205: }
! 206:
! 207: /* ...and allocated list. */
! 208: while ((m = TAILQ_FIRST(&allocatedlist)) != NULL)) {
! 209: LIST_REMOVE(m, list);
! 210: OF_release(m, m->size);
! 211: }
! 212: #endif /* __notyet__ */
! 213: }
CVSweb
![[BACK]](/icons/back.gif){kind=icon}
Return to alloc.c CVS log ![[TXT]](/icons/text.gif){kind=icon}
![[DIR]](/icons/dir.gif){kind=icon}
Up to [local] / sys / arch / sparc64 / stand / ofwboot