Goto sanos source index
//
// rmap.c
//
// Routines for working with a resource map
//
// Copyright (C) 2002 Michael Ringgaard. All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
//
// 1. Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// 2. Redistributions in binary form must reproduce the above copyright
// notice, this list of conditions and the following disclaimer in the
// documentation and/or other materials provided with the distribution.
// 3. Neither the name of the project nor the names of its contributors
// may be used to endorse or promote products derived from this software
// without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
// IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
// ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
// OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
// HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
// LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
// OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
// SUCH DAMAGE.
//
//
// The first entry in a resource map is interpreted as a header.
// The r_size field tells how many slots the overall data structure
// has; r_off tells how many non-empty elements exist.
//
// The list is kept in ascending order with all non-empty elements
// first.
//
#include <stdarg.h>
#include <sys/types.h>
#include <string.h>
#include <rmap.h>
unsigned int lost_elems = 0L; // Diagnostic for space lost due to fragmentation
//
// Initialize the named resource map
//
// "size" is the total size, including the element we will use
// as the header.
//
void rmap_init(struct rmap *rmap, unsigned int size) {
// Record # slots available, which is one less (since we use the first as our own header).
rmap->offset = 0;
rmap->size = size - 1;
}
//
// Insert room for a new slot at the given position
//
// Returns 1 if there isn't room to insert the element, 0 on success.
//
static int makespace(struct rmap *rmap, struct rmap *r) {
struct rmap *rlim = &rmap[rmap->offset];
// If no room to insert slot, return failure
if (rmap->size == rmap->offset) return 1;
rmap->offset += 1;
// If inserting in middle, slide up entries
if (r <= rlim) {
memmove(r + 1, r, sizeof(struct rmap) * ((rlim - r) + 1));
return 0;
}
return 0;
}
//
// An entry has been emptied, so make it disappear
//
static void collapse(struct rmap *rmap, struct rmap *r) {
struct rmap *rlim = &rmap[rmap->offset];
rmap->offset -= 1;
if (r < rlim) memmove(r, r + 1, sizeof(struct rmap) * (rlim - r));
}
//
// Allocate some space from a resource map
//
// Returns 0 on failure. Thus, you can't store index 0 in a resource map
//
unsigned int rmap_alloc(struct rmap *rmap, unsigned int size) {
struct rmap *r, *rlim;
unsigned int idx;
// Find first slot with a fit, return failure if we run off the
// end of the list without finding a fit.
rlim = &rmap[rmap->offset];
for (r = &rmap[1]; r <= rlim; r++) {
if (r->size >= size) break;
}
if (r > rlim) return 0;
// Trim the resource element if it still has some left,
// otherwise delete from the list.
idx = r->offset;
if (r->size > size) {
r->offset += size;
r->size -= size;
} else {
collapse(rmap, r);
}
return idx;
}
//
// Allocate some aligned space from a resource map
//
// Returns 0 on failure.
//
unsigned int rmap_alloc_align(struct rmap *rmap, unsigned int size, unsigned int align) {
struct rmap *r, *rlim;
unsigned int idx;
unsigned int gap;
// Find first slot with a fit, return failure if we run off the
// end of the list without finding a fit.
rlim = &rmap[rmap->offset];
for (r = &rmap[1]; r <= rlim; r++) {
if (r->offset % align == 0) {
gap = 0;
} else {
gap = align - (r->offset % align);
}
if (r->size >= size + gap) break;
}
if (r > rlim) return 0;
idx = r->offset + gap;
// Reserve region
if (rmap_reserve(rmap, idx, size)) {
return 0;
} else {
return idx;
}
}
//
// Free some space back into the resource map
//
// The list is kept ordered, with the first free element flagged
// with a size of 0.
//
void rmap_free(struct rmap *rmap, unsigned int offset, unsigned int size) {
struct rmap *r, *rlim;
// Scan forward until we find the place we should be inserted.
rlim = &rmap[rmap->offset];
for (r = &rmap[1]; r <= rlim; r++) {
// If the new free space abuts this entry, tack it on and return.
if ((r->offset + r->size) == offset) {
r->size += size;
// If this entry now abuts the next, coalesce
if ((r < rlim) && ((r->offset + r->size) == (r[1].offset))) {
r->size += r[1].size;
rmap->offset -= 1;
r++;
if (r < rlim) memmove(r, r + 1, sizeof(struct rmap) * (rlim - r));
}
return;
}
// If this space abuts the entry, pad it onto the beginning.
if ((offset + size) == r->offset) {
r->size += size;
r->offset = offset;
return;
}
if (offset < r->offset) break;
}
// Need to add a new element. See if it'll fit.
if (makespace(rmap, r)) {
// Nope. Tabulate and lose the space.
lost_elems += size;
return;
}
// Record it
r->offset = offset;
r->size = size;
}
//
// Reserve the requested range, or return failure if any of it is not free
//
// Returns 0 on success, 1 on failure.
//
int rmap_reserve(struct rmap *rmap, unsigned int offset, unsigned int size) {
struct rmap *r, *rlim;
unsigned int top, rtop;
rlim = &rmap[rmap->offset];
for (r = &rmap[1]; r <= rlim; r++) {
// If we've advanced beyond the requested offset,
// we can never match, so end the loop.
if (r->offset > offset) break;
// See if this is the range which will hold our request
top = r->offset + r->size;
if (!((r->offset <= offset) && (top > offset))) continue;
// Since this run encompasses the requested range, we
// can either grab all of it, or none of it.
// The top of our request extends beyond the block; fail.
rtop = offset + size;
if (rtop > top) return 1;
// If the requested start matches our range's start, we
// can simply shave it off the front.
if (offset == r->offset) {
r->offset += size;
r->size -= size;
if (r->size == 0) collapse(rmap, r);
return 0;
}
// Similarly, if the end matches, we can shave the end
if (rtop == top) {
r->size -= size;
// We know r->size > 0, since otherwise we would've
// matched the previous case otherwise.
return 0;
}
// Otherwise we must split the range
if (makespace(rmap, r)) {
unsigned int osize;
// No room for further fragmentation, so chop off to the tail.
osize = r->size;
r->size = top - rtop;
lost_elems += (osize - r->size) - size;
r->offset = rtop;
return 0;
}
// The current slot is everything below us
r->size = offset - r->offset;
// The new slot is everything above
r++;
r->offset = rtop;
r->size = top - rtop;
// OK
return 0;
}
// Nope, not in our range of free entries
return 1;
}
//
// Checks allocation status for a resource region
//
// Returns 0 if free, 1 if allocated, -1 if partially allocated.
//
int rmap_status(struct rmap *rmap, unsigned int offset, unsigned int size) {
struct rmap *r, *rlim;
unsigned int top, rtop;
rlim = &rmap[rmap->offset];
for (r = &rmap[1]; r <= rlim; r++) {
// If we've advanced beyond the requested offset,
// we can never match, check for partially allocated.
if (r->offset > offset) {
if (offset + size > r->offset) {
return -1;
} else {
return 1;
}
}
// See if this is the range which will hold our request
top = r->offset + r->size;
if (!((r->offset <= offset) && (top > offset))) continue;
// Check allocation status
rtop = offset + size;
if (rtop < top) {
return 0;
} else {
return -1;
}
}
// Resource region is allocated
return 1;
}