Return to rmap.c CVS log

Up to [Research Unix] / researchv10dc / lsys / os

Annotation of researchv10dc/lsys/os/rmap.c, revision 1.1

1.1     ! root        1: #include "sys/param.h"
        !             2: #include "sys/map.h"
        !             3: #include "sys/dmap.h"
        !             4: 
        !             5: /*
        !             6:  * resource maps, for dishing out pieces of things
        !             7:  * that can be described by integers
        !             8:  *
        !             9:  * to use them:
        !            10:  * declare struct map xxmap[N]
        !            11:  * where N is the largest number of pieces free parts of the resource may be
        !            12:  * fragmented into
        !            13:  *     rminit to set up the map
        !            14:  *     rmalloc to allocate pieces
        !            15:  *     rmfree to give them back
        !            16:  *
        !            17:  * the map is an array of (size, address) pairs,
        !            18:  * ordered by address.
        !            19:  * allocation is first-fit.
        !            20:  * if the map becomes very fragmented,
        !            21:  * and therefore too big to fit,
        !            22:  * some of the resource may be lost.
        !            23:  * the first piece of the map is magic, and holds an end-marker;
        !            24:  * the last piece is kept empty
        !            25:  */
        !            26: 
        !            27: /*
        !            28:  * initialize struct map mp[mapsize]
        !            29:  * to hold size pieces starting at addr
        !            30:  */
        !            31: rminit(mp, mapsize, size, addr)
        !            32:        register struct map *mp;
        !            33:        int mapsize;
        !            34:        int size, addr;
        !            35: {
        !            36: 
        !            37:        if (mapsize < 3)
        !            38:                panic("rminit");
        !            39:        mp->m_end = mapsize - 1;        /* leave an end-marker */
        !            40:        mp++;
        !            41:        mp->m_size = size;
        !            42:        mp->m_addr = addr;
        !            43:        mp++;
        !            44:        mp->m_size = 0;
        !            45:        mp->m_addr = 0;
        !            46: }
        !            47: 
        !            48: rmalloc(mp, size)
        !            49:        register struct map *mp;
        !            50: {
        !            51:        register int addr;
        !            52:        register struct map *bp;
        !            53: 
        !            54:        if (size <= 0)
        !            55:                panic("rmalloc");
        !            56:        for (bp = mp+1; bp->m_size; bp++) {
        !            57:                if (bp->m_size >= size) {
        !            58:                        addr = bp->m_addr;
        !            59:                        bp->m_addr += size;
        !            60:                        if ((bp->m_size -= size) == 0) {
        !            61:                                do {
        !            62:                                        bp++;
        !            63:                                        (bp-1)->m_addr = bp->m_addr;
        !            64:                                } while ((bp-1)->m_size = bp->m_size);
        !            65:                        }
        !            66:                        return (addr);
        !            67:                }
        !            68:        }
        !            69:        return (0);
        !            70: }
        !            71: 
        !            72: /*
        !            73:  * special version of rmalloc, to handle swapmap silliness
        !            74:  * historical; get rid of it later
        !            75:  */
        !            76: srmalloc(mp, size)
        !            77:        register struct map *mp;
        !            78: {
        !            79:        register int addr;
        !            80:        register struct map *bp;
        !            81:        swblk_t first, rest;
        !            82: 
        !            83:        if (size <= 0 || size > dmmax)
        !            84:                panic("rmalloc");
        !            85:        for (bp = mp+1; bp->m_size; bp++) {
        !            86:                if (bp->m_size >= size) {
        !            87:                        /*
        !            88:                         * If allocating from swapmap,
        !            89:                         * then have to respect interleaving
        !            90:                         * boundaries.
        !            91:                         */
        !            92:                        if ((first = dmmax - bp->m_addr%dmmax) < bp->m_size) {
        !            93:                                if (bp->m_size - first < size)
        !            94:                                        continue;
        !            95:                                addr = bp->m_addr + first;
        !            96:                                rest = bp->m_size - first - size;
        !            97:                                bp->m_size = first;
        !            98:                                if (rest)
        !            99:                                        rmfree(mp, rest, addr+size);
        !           100:                                return (addr);
        !           101:                        }
        !           102:                        addr = bp->m_addr;
        !           103:                        bp->m_addr += size;
        !           104:                        if ((bp->m_size -= size) == 0) {
        !           105:                                do {
        !           106:                                        bp++;
        !           107:                                        (bp-1)->m_addr = bp->m_addr;
        !           108:                                } while ((bp-1)->m_size = bp->m_size);
        !           109:                        }
        !           110:                        if (addr % CLSIZE)
        !           111:                                panic("rmalloc swapmap");
        !           112:                        return (addr);
        !           113:                }
        !           114:        }
        !           115:        return (0);
        !           116: }
        !           117: 
        !           118: /*
        !           119:  * free a chunk
        !           120:  * hack: if we need to create a new map entry
        !           121:  * and there aren't any left,
        !           122:  * discard the next-to-last,
        !           123:  * as the last one tends to be larger
        !           124:  */
        !           125: rmfree(mp, size, addr)
        !           126:        register struct map *mp;
        !           127:        register int size, addr;
        !           128: {
        !           129:        register struct map *bp, *xp;
        !           130: 
        !           131:        if (addr <= 0 || size <= 0)
        !           132:                panic("rmfree");
        !           133:        for (bp = mp + 1; bp->m_addr <= addr && bp->m_size != 0; bp++)
        !           134:                continue;
        !           135:        /*
        !           136:         * can merge into previous block, or both sides?
        !           137:         */
        !           138:        xp = bp - 1;
        !           139:        if (bp > mp + 1 && xp->m_addr + xp->m_size >= addr) {
        !           140:                if (xp->m_addr + xp->m_size > addr)
        !           141:                        panic("dup rmfree");
        !           142:                xp->m_size += size;
        !           143:                if (bp->m_addr && addr+size >= bp->m_addr) {
        !           144:                        if (addr+size > bp->m_addr)
        !           145:                                panic("dup rmfree");
        !           146:                        xp->m_size += bp->m_size;
        !           147:                        while (bp->m_size) {
        !           148:                                bp[0] = bp[1];
        !           149:                                bp++;
        !           150:                        }
        !           151:                }
        !           152:                return;
        !           153:        }
        !           154:        /*
        !           155:         * can merge into next block?
        !           156:         */
        !           157:        if (addr+size >= bp->m_addr && bp->m_size) {
        !           158:                if (addr+size > bp->m_addr)
        !           159:                        panic("dup rmfree");
        !           160:                bp->m_addr -= size;
        !           161:                bp->m_size += size;
        !           162:                return;
        !           163:        }
        !           164:        /*
        !           165:         * can't merge; make a new entry before bp
        !           166:         */
        !           167:        xp = bp;
        !           168:        while (bp->m_size)
        !           169:                bp++;
        !           170:        if (bp-mp >= mp->m_end) {       /* overflow? */
        !           171:                printf("rmfree: map %x overflow, lost %d-%d\n", mp,
        !           172:                        bp[-2].m_addr, bp[-2].m_size+bp[-2].m_addr);
        !           173:                bp[-2] = bp[-1];
        !           174:                bp[-1] = bp[0];
        !           175:                bp--;
        !           176:        }
        !           177:        do {
        !           178:                bp[1] = bp[0];
        !           179:                bp--;
        !           180:        } while (bp >= xp);
        !           181:        xp->m_size = size;
        !           182:        xp->m_addr = addr;
        !           183: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.