From b725a0caed0e5e642ad56eca5a13c8c68996a127 Mon Sep 17 00:00:00 2001 From: Bill Joy Date: Sun, 1 Mar 1981 01:17:52 -0800 Subject: [PATCH 1/1] changes for rmalloc, rmfree, malloc.c SCCS-vsn: sys/kern/kern_proc.c 4.8 SCCS-vsn: sys/kern/subr_rmap.c 4.2 SCCS-vsn: sys/kern/subr_rmap.c.sav 4.2 SCCS-vsn: sys/kern/subr_prf.c 4.11 --- usr/src/sys/kern/kern_proc.c | 8 +- usr/src/sys/kern/subr_prf.c | 73 ++++++---- usr/src/sys/kern/subr_rmap.c | 237 ++++++++++++++++++++++++------- usr/src/sys/kern/subr_rmap.c.sav | 237 ++++++++++++++++++++++++------- 4 files changed, 423 insertions(+), 132 deletions(-) diff --git a/usr/src/sys/kern/kern_proc.c b/usr/src/sys/kern/kern_proc.c index 06600e05b3..920b9f77dc 100644 --- a/usr/src/sys/kern/kern_proc.c +++ b/usr/src/sys/kern/kern_proc.c @@ -1,4 +1,4 @@ -/* kern_proc.c 4.7 %G% */ +/* kern_proc.c 4.8 %G% */ #include "../h/param.h" #include "../h/systm.h" @@ -169,12 +169,12 @@ exece() ne = 0; nc = 0; uap = (struct execa *)u.u_ap; - if ((bno = malloc(argmap, ctod(clrnd((int) btoc(NCARGS))))) == 0) { + if ((bno = rmalloc(argmap, ctod(clrnd((int) btoc(NCARGS))))) == 0) { swkill(u.u_procp, "exece"); goto bad; } if (bno % CLSIZE) - panic("execa malloc"); + panic("execa rmalloc"); if (uap->argp) for (;;) { ap = NULL; if (na == 1 && indir) { @@ -280,7 +280,7 @@ bad: if (bp) brelse(bp); if (bno) - mfree(argmap, ctod(clrnd((int) btoc(NCARGS))), bno); + rmfree(argmap, ctod(clrnd((int) btoc(NCARGS))), bno); iput(ip); } diff --git a/usr/src/sys/kern/subr_prf.c b/usr/src/sys/kern/subr_prf.c index cb390fa456..f680c6e3b7 100644 --- a/usr/src/sys/kern/subr_prf.c +++ b/usr/src/sys/kern/subr_prf.c @@ -1,4 +1,4 @@ -/* subr_prf.c 4.10 %G% */ +/* subr_prf.c 4.11 %G% */ #include "../h/param.h" #include "../h/systm.h" @@ -18,46 +18,52 @@ * panicstr contains argument to last * call to panic. */ - char *panicstr; /* * Scaled down version of C Library printf. - * Only %s %u %d (==%u) %o %x %D are recognized. - * Used to print diagnostic information - * directly on console tty. - * Since it is not interrupt driven, - * all system activities are pretty much - * suspended. - * Printf should not be used for chit-chat. + * Used to print diagnostic information directly on console tty. + * Since it is not interrupt driven, all system activities are + * suspended. Printf should not be used for chit-chat. + * + * One additional format: %b is supported to decode error registers. + * Usage is: + * printf("reg=%b\n", regval, "*"); + * Where is the output base expressed as a control character, + * e.g. \10 gives octal; \20 gives hex. Each arg is a sequence of + * characters, the first of which gives the bit number to be inspected + * (origin 1), and the next characters (up to a control character, i.e. + * a character <= 32), give the name of the register. Thus + * printf("reg=%b\n", 3, "\10\2BITTWO\1BITONE\n"); + * would produce output: + * reg=2 */ /*VARARGS1*/ printf(fmt, x1) -register char *fmt; -unsigned x1; + char *fmt; + unsigned x1; { prf(fmt, &x1, 0); } /* - * print to the current users terminal, - * guarantee not to sleep (so can be called by intr routine) - * no watermark checking - so no verbose messages + * Uprintf prints to the current user's terminal, + * guarantees not to sleep (so can be called by interrupt routines) + * and does no watermark checking - (so no verbose messages). */ /*VARARGS1*/ uprintf(fmt, x1) - char *fmt; + char *fmt; unsigned x1; { prf(fmt, &x1, 2); } -/* THIS CODE IS VAX DEPENDENT */ prf(fmt, adx, touser) -register char *fmt; -register u_int *adx; + register char *fmt; + register u_int *adx; { register int b, c, i; char *s; @@ -71,6 +77,7 @@ loop: } again: c = *fmt++; + /* THIS CODE IS VAX DEPENDENT IN HANDLING %l? AND %c */ switch (c) { case 'l': @@ -124,8 +131,11 @@ number: adx++; goto loop; } -/* END VAX DEPENDENT CODE */ +/* + * Printn prints a number n in base b. + * We don't use recursion to avoid deep kernel stacks. + */ printn(n, b, touser) unsigned long n; { @@ -148,24 +158,26 @@ printn(n, b, touser) /* * Panic is called on unresolvable fatal errors. - * It syncs, prints "panic: mesg", and then reboots. + * It prints "panic: mesg", and then reboots. + * If we are called twice, then we avoid trying to + * sync the disks as this often leads to recursive panics. */ panic(s) -char *s; + char *s; { + int bootopt = panicstr ? RB_AUTOBOOT : RB_AUTOBOOT|RB_NOSYNC; panicstr = s; printf("panic: %s\n", s); (void) spl0(); - for(;;) - boot(RB_PANIC, RB_AUTOBOOT); + boot(RB_PANIC, bootopt); } /* - * prdev prints a warning message of the - * form "mesg on dev x/y". - * x and y are the major and minor parts of - * the device argument. + * Prdev prints a warning message of the form "mesg on dev x/y". + * x and y are the major and minor parts of the device argument. + * + * PRDEV SHOULD COMPUTE AND USE DEVICE NAMES */ prdev(str, dev) char *str; @@ -175,12 +187,17 @@ prdev(str, dev) printf("%s on dev %d/%d\n", str, major(dev), minor(dev)); } +/* + * Hard error is the preface to plaintive error messages + * about failing device transfers. + */ harderr(bp) struct buf *bp; { - printf("hard err bn %d ", bp->b_blkno); + printf("hard err bn%d ", bp->b_blkno); } + /* * Print a character on console or users terminal. * If destination is console then the last MSGBUFS characters diff --git a/usr/src/sys/kern/subr_rmap.c b/usr/src/sys/kern/subr_rmap.c index 5979a0d855..ee287c61f2 100644 --- a/usr/src/sys/kern/subr_rmap.c +++ b/usr/src/sys/kern/subr_rmap.c @@ -1,4 +1,4 @@ -/* subr_rmap.c 4.1 %G% */ +/* subr_rmap.c 4.2 %G% */ #include "../h/param.h" #include "../h/systm.h" @@ -9,38 +9,115 @@ #include "../h/mtpr.h" #include "../h/text.h" +/* + * Resource map handling routines. + * + * A resource map is an array of structures each + * of which describes a segment of the address space of an available + * resource. The segments are described by their base address and + * length, and sorted in address order. Each resource map has a fixed + * maximum number of segments allowed. Resources are allocated + * by taking part or all of one of the segments of the map. + * + * Returning of resources will require another segment if + * the returned resources are not adjacent in the address + * space to an existing segment. If the return of a segment + * would require a slot which is not available, then one of + * the resource map segments is discarded after a warning is printed. + * Returning of resources may also cause the map to collapse + * by coalescing two existing segments and the returned space + * into a single segment. In this case the resource map is + * made smaller by copying together to fill the resultant gap. + * + * N.B.: the current implementation uses a dense array and does + * not admit the value ``0'' as a legal address, since that is used + * as a delimiter. + */ + +/* + * Initialize map mp to have (mapsize-2) segments + * and to be called ``name'', which we print if + * the slots become so fragmented that we lose space. + * The map itself is initialized with size elements free + * starting at addr. + */ +rminit(mp, size, addr, name, mapsize) + register struct map *mp; + int size, addr; + char *name; + int mapsize; +{ + register struct mapent *ep = (struct mapent *)(mp+1); + + mp->m_name = name; +/* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ + /* + * One of the mapsize slots is taken by the map structure, + * segments has size 0 and addr 0, and acts as a delimiter. + * We insure that we never use segments past the end of + * the array which is given by mp->m_limit. + * Instead, when excess segments occur we discard some resources. + */ + mp->m_limit = (struct mapent *)&mp[mapsize]; + /* + * Simulate a rmfree(), but with the option to + * call with size 0 and addr 0 when we just want + * to initialize without freeing. + */ + ep->m_size = size; + ep->m_addr = addr; +} + /* * Allocate 'size' units from the given - * map. Return the base of the allocated - * space. + * map. Return the base of the allocated space. * In a map, the addresses are increasing and the * list is terminated by a 0 size. - * The swap map unit is 512 bytes. + * * Algorithm is first-fit. + * + * This routine knows about the interleaving of the swapmap + * and handles that. */ -malloc(mp, size) -struct map *mp; +rmalloc(mp, size) + register struct map *mp; { - register int a; - register struct map *bp; + register struct mapent *ep = (struct mapent *)(mp+1); + register int addr; + register struct mapent *bp; swblk_t first, rest; if (size <= 0 || mp == swapmap && size > DMMAX) - panic("malloc"); - for (bp=mp; bp->m_size; bp++) { + panic("rmalloc"); + /* + * Search for a piece of the resource map which has enough + * free space to accomodate the request. + */ + for (bp = ep; bp->m_size; bp++) { if (bp->m_size >= size) { + /* + * If allocating from swapmap, + * then have to respect interleaving + * boundaries. + */ if (mp == swapmap && (first = DMMAX - bp->m_addr%DMMAX) < bp->m_size) { if (bp->m_size - first < size) continue; - a = bp->m_addr + first; + addr = bp->m_addr + first; rest = bp->m_size - first - size; bp->m_size = first; if (rest) - mfree(swapmap, rest, a+size); - return (a); + rmfree(swapmap, rest, addr+size); + return (addr); } - a = bp->m_addr; + /* + * Allocate from the map. + * If there is no space left of the piece + * we allocated from, move the rest of + * the pieces to the left. + */ + addr = bp->m_addr; bp->m_addr += size; if ((bp->m_size -= size) == 0) { do { @@ -48,41 +125,63 @@ struct map *mp; (bp-1)->m_addr = bp->m_addr; } while ((bp-1)->m_size = bp->m_size); } - if (mp == swapmap && a % CLSIZE) - panic("malloc swapmap"); - return(a); + if (mp == swapmap && addr % CLSIZE) + panic("rmalloc swapmap"); + return (addr); } } - return(0); + return (0); } /* - * Free the previously allocated space aa + * Free the previously allocated space at addr * of size units into the specified map. - * Sort aa into map and combine on + * Sort addr into map and combine on * one or both ends if possible. */ -mfree(mp, size, a) -struct map *mp; -register int size, a; +rmfree(mp, size, addr) + struct map *mp; + register int size, addr; { - register struct map *bp; + struct mapent *firstbp; + register struct mapent *bp; register int t; - if (a <= 0) - panic("mfree addr"); - if (size <= 0) - panic("mfree size"); - bp = mp; - for (; bp->m_addr<=a && bp->m_size!=0; bp++) + /* + * Both address and size must be + * positive, or the protocol has broken down. + */ + if (addr <= 0 || size <= 0) + goto badrmfree; + /* + * Locate the piece of the map which starts after the + * returned space (or the end of the map). + */ + firstbp = bp = (struct mapent *)(mp + 1); + for (; bp->m_addr <= addr && bp->m_size != 0; bp++) continue; - if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size > a) - panic("mfree begov"); - if (a+size > bp->m_addr && bp->m_size) - panic("mfree endov"); - if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size == a) { + /* + * If the piece on the left abuts us, + * then we should combine with it. + */ + if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { + /* + * Check no overlap (internal error). + */ + if ((bp-1)->m_addr+(bp-1)->m_size > addr) + goto badrmfree; + /* + * Add into piece on the left by increasing its size. + */ (bp-1)->m_size += size; - if (a+size == bp->m_addr) { + /* + * If the combined piece abuts the piece on + * the right now, compress it in also, + * by shifting the remaining pieces of the map over. + */ + if (bp->m_addr && addr+size >= bp->m_addr) { + if (addr+size > bp->m_addr) + goto badrmfree; (bp-1)->m_size += bp->m_size; while (bp->m_size) { bp++; @@ -90,23 +189,61 @@ register int size, a; (bp-1)->m_size = bp->m_size; } } - } else { - if (a+size == bp->m_addr && bp->m_size) { - bp->m_addr -= size; - bp->m_size += size; - } else if (size) { - do { - t = bp->m_addr; - bp->m_addr = a; - a = t; - t = bp->m_size; - bp->m_size = size; - bp++; - } while (size = t); - } + goto done; + } + /* + * Don't abut on the left, check for abutting on + * the right. + */ + if (addr+size >= bp->m_addr && bp->m_size) { + if (addr+size > bp->m_addr) + goto badrmfree; + bp->m_addr -= size; + bp->m_size += size; + goto done; + } + /* + * Don't abut at all. Make a new entry + * and check for map overflow. + */ + do { + t = bp->m_addr; + bp->m_addr = addr; + addr = t; + t = bp->m_size; + bp->m_size = size; + bp++; + } while (size = t); + /* + * Segment at bp is to be the delimiter; + * If there is not room for it + * then the table is too full + * and we must discard something. + */ + if (bp+1 > mp->m_limit) { + /* + * Back bp up to last available segment. + * which contains a segment already and must + * be made into the delimiter. + * Discard second to last entry, + * since it is presumably smaller than the last + * and move the last entry back one. + */ + bp--; + printf("%s rmap overflow, lost [%d,%d)\n", mp->m_name, + (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); + bp[-1] = bp[0]; + bp[0].m_size = bp[0].m_addr = 0; } +done: + /* + * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE! + */ if ((mp == kernelmap) && kmapwnt) { kmapwnt = 0; wakeup((caddr_t)kernelmap); } + return; +badrmfree: + panic("bad rmfree"); } diff --git a/usr/src/sys/kern/subr_rmap.c.sav b/usr/src/sys/kern/subr_rmap.c.sav index 4724e9ceb1..187bc193dc 100644 --- a/usr/src/sys/kern/subr_rmap.c.sav +++ b/usr/src/sys/kern/subr_rmap.c.sav @@ -1,4 +1,4 @@ -/* subr_rmap.c.sav 4.1 %G% */ +/* subr_rmap.c.sav 4.2 %G% */ #include "../h/param.h" #include "../h/systm.h" @@ -9,38 +9,115 @@ #include "../h/mtpr.h" #include "../h/text.h" +/* + * Resource map handling routines. + * + * A resource map is an array of structures each + * of which describes a segment of the address space of an available + * resource. The segments are described by their base address and + * length, and sorted in address order. Each resource map has a fixed + * maximum number of segments allowed. Resources are allocated + * by taking part or all of one of the segments of the map. + * + * Returning of resources will require another segment if + * the returned resources are not adjacent in the address + * space to an existing segment. If the return of a segment + * would require a slot which is not available, then one of + * the resource map segments is discarded after a warning is printed. + * Returning of resources may also cause the map to collapse + * by coalescing two existing segments and the returned space + * into a single segment. In this case the resource map is + * made smaller by copying together to fill the resultant gap. + * + * N.B.: the current implementation uses a dense array and does + * not admit the value ``0'' as a legal address, since that is used + * as a delimiter. + */ + +/* + * Initialize map mp to have (mapsize-2) segments + * and to be called ``name'', which we print if + * the slots become so fragmented that we lose space. + * The map itself is initialized with size elements free + * starting at addr. + */ +rminit(mp, size, addr, name, mapsize) + register struct map *mp; + int size, addr; + char *name; + int mapsize; +{ + register struct mapent *ep = (struct mapent *)(mp+1); + + mp->m_name = name; +/* N.B.: WE ASSUME HERE THAT sizeof (struct map) == sizeof (struct mapent) */ + /* + * One of the mapsize slots is taken by the map structure, + * segments has size 0 and addr 0, and acts as a delimiter. + * We insure that we never use segments past the end of + * the array which is given by mp->m_limit. + * Instead, when excess segments occur we discard some resources. + */ + mp->m_limit = (struct mapent *)&mp[mapsize]; + /* + * Simulate a rmfree(), but with the option to + * call with size 0 and addr 0 when we just want + * to initialize without freeing. + */ + ep->m_size = size; + ep->m_addr = addr; +} + /* * Allocate 'size' units from the given - * map. Return the base of the allocated - * space. + * map. Return the base of the allocated space. * In a map, the addresses are increasing and the * list is terminated by a 0 size. - * The swap map unit is 512 bytes. + * * Algorithm is first-fit. + * + * This routine knows about the interleaving of the swapmap + * and handles that. */ -malloc(mp, size) -struct map *mp; +rmalloc(mp, size) + register struct map *mp; { - register int a; - register struct map *bp; + register struct mapent *ep = (struct mapent *)(mp+1); + register int addr; + register struct mapent *bp; swblk_t first, rest; if (size <= 0 || mp == swapmap && size > DMMAX) - panic("malloc"); - for (bp=mp; bp->m_size; bp++) { + panic("rmalloc"); + /* + * Search for a piece of the resource map which has enough + * free space to accomodate the request. + */ + for (bp = ep; bp->m_size; bp++) { if (bp->m_size >= size) { + /* + * If allocating from swapmap, + * then have to respect interleaving + * boundaries. + */ if (mp == swapmap && (first = DMMAX - bp->m_addr%DMMAX) < bp->m_size) { if (bp->m_size - first < size) continue; - a = bp->m_addr + first; + addr = bp->m_addr + first; rest = bp->m_size - first - size; bp->m_size = first; if (rest) - mfree(swapmap, rest, a+size); - return (a); + rmfree(swapmap, rest, addr+size); + return (addr); } - a = bp->m_addr; + /* + * Allocate from the map. + * If there is no space left of the piece + * we allocated from, move the rest of + * the pieces to the left. + */ + addr = bp->m_addr; bp->m_addr += size; if ((bp->m_size -= size) == 0) { do { @@ -48,41 +125,63 @@ struct map *mp; (bp-1)->m_addr = bp->m_addr; } while ((bp-1)->m_size = bp->m_size); } - if (mp == swapmap && a % CLSIZE) - panic("malloc swapmap"); - return(a); + if (mp == swapmap && addr % CLSIZE) + panic("rmalloc swapmap"); + return (addr); } } - return(0); + return (0); } /* - * Free the previously allocated space aa + * Free the previously allocated space at addr * of size units into the specified map. - * Sort aa into map and combine on + * Sort addr into map and combine on * one or both ends if possible. */ -mfree(mp, size, a) -struct map *mp; -register int size, a; +rmfree(mp, size, addr) + struct map *mp; + register int size, addr; { - register struct map *bp; + struct mapent *firstbp; + register struct mapent *bp; register int t; - if (a <= 0) - panic("mfree addr"); - if (size <= 0) - panic("mfree size"); - bp = mp; - for (; bp->m_addr<=a && bp->m_size!=0; bp++) + /* + * Both address and size must be + * positive, or the protocol has broken down. + */ + if (addr <= 0 || size <= 0) + goto badrmfree; + /* + * Locate the piece of the map which starts after the + * returned space (or the end of the map). + */ + firstbp = bp = (struct mapent *)(mp + 1); + for (; bp->m_addr <= addr && bp->m_size != 0; bp++) continue; - if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size > a) - panic("mfree begov"); - if (a+size > bp->m_addr && bp->m_size) - panic("mfree endov"); - if (bp>mp && (bp-1)->m_addr+(bp-1)->m_size == a) { + /* + * If the piece on the left abuts us, + * then we should combine with it. + */ + if (bp > firstbp && (bp-1)->m_addr+(bp-1)->m_size >= addr) { + /* + * Check no overlap (internal error). + */ + if ((bp-1)->m_addr+(bp-1)->m_size > addr) + goto badrmfree; + /* + * Add into piece on the left by increasing its size. + */ (bp-1)->m_size += size; - if (a+size == bp->m_addr) { + /* + * If the combined piece abuts the piece on + * the right now, compress it in also, + * by shifting the remaining pieces of the map over. + */ + if (bp->m_addr && addr+size >= bp->m_addr) { + if (addr+size > bp->m_addr) + goto badrmfree; (bp-1)->m_size += bp->m_size; while (bp->m_size) { bp++; @@ -90,23 +189,61 @@ register int size, a; (bp-1)->m_size = bp->m_size; } } - } else { - if (a+size == bp->m_addr && bp->m_size) { - bp->m_addr -= size; - bp->m_size += size; - } else if (size) { - do { - t = bp->m_addr; - bp->m_addr = a; - a = t; - t = bp->m_size; - bp->m_size = size; - bp++; - } while (size = t); - } + goto done; + } + /* + * Don't abut on the left, check for abutting on + * the right. + */ + if (addr+size >= bp->m_addr && bp->m_size) { + if (addr+size > bp->m_addr) + goto badrmfree; + bp->m_addr -= size; + bp->m_size += size; + goto done; + } + /* + * Don't abut at all. Make a new entry + * and check for map overflow. + */ + do { + t = bp->m_addr; + bp->m_addr = addr; + addr = t; + t = bp->m_size; + bp->m_size = size; + bp++; + } while (size = t); + /* + * Segment at bp is to be the delimiter; + * If there is not room for it + * then the table is too full + * and we must discard something. + */ + if (bp+1 > mp->m_limit) { + /* + * Back bp up to last available segment. + * which contains a segment already and must + * be made into the delimiter. + * Discard second to last entry, + * since it is presumably smaller than the last + * and move the last entry back one. + */ + bp--; + printf("%s rmap overflow, lost [%d,%d)\n", mp->m_name, + (bp-1)->m_addr, (bp-1)->m_addr+(bp-1)->m_size); + bp[-1] = bp[0]; + bp[0].m_size = bp[0].m_addr = 0; } +done: + /* + * THIS IS RIDICULOUS... IT DOESN'T BELONG HERE! + */ if ((mp == kernelmap) && kmapwnt) { kmapwnt = 0; wakeup((caddr_t)kernelmap); } + return; +badrmfree: + panic("bad rmfree"); } -- 2.20.1