/* subr_rmap.c 4.8 82/10/21 */
* 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
* 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
rminit(mp
, size
, addr
, name
, mapsize
)
register struct mapent
*ep
= (struct mapent
*)(mp
+1);
/* 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.
* Allocate 'size' units from the given
* map. Return the base of the allocated space.
* In a map, the addresses are increasing and the
* list is terminated by a 0 size.
* Algorithm is first-fit.
* This routine knows about the interleaving of the swapmap
register struct mapent
*ep
= (struct mapent
*)(mp
+1);
register struct mapent
*bp
;
if (size
<= 0 || mp
== swapmap
&& size
> DMMAX
)
* 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
(first
= DMMAX
- bp
->m_addr
%DMMAX
) < bp
->m_size
) {
if (bp
->m_size
- first
< size
)
addr
= bp
->m_addr
+ first
;
rest
= bp
->m_size
- first
- size
;
rmfree(swapmap
, rest
, addr
+size
);
* If there is no space left of the piece
* we allocated from, move the rest of
* the pieces to the left.
if ((bp
->m_size
-= size
) == 0) {
(bp
-1)->m_addr
= bp
->m_addr
;
} while ((bp
-1)->m_size
= bp
->m_size
);
if (mp
== swapmap
&& addr
% CLSIZE
)
panic("rmalloc swapmap");
* Free the previously allocated space at addr
* of size units into the specified map.
* Sort addr into map and combine on
* one or both ends if possible.
register struct mapent
*bp
;
* Both address and size must be
* positive, or the protocol has broken down.
if (addr
<= 0 || size
<= 0)
* 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
++)
* 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
)
* Add into piece on the left by increasing its size.
* 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
)
(bp
-1)->m_size
+= bp
->m_size
;
(bp
-1)->m_addr
= bp
->m_addr
;
(bp
-1)->m_size
= bp
->m_size
;
* Don't abut on the left, check for abutting on
if (addr
+size
>= bp
->m_addr
&& bp
->m_size
) {
if (addr
+size
> bp
->m_addr
)
* Don't abut at all. Make a new entry
* and check for map overflow.
* 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.
printf("%s: rmap ovflo, lost [%d,%d)\n", mp
->m_name
,
(bp
-1)->m_addr
, (bp
-1)->m_addr
+(bp
-1)->m_size
);
bp
[0].m_size
= bp
[0].m_addr
= 0;
* THIS IS RIDICULOUS... IT DOESN'T BELONG HERE!
if ((mp
== kernelmap
) && kmapwnt
) {
wakeup((caddr_t
)kernelmap
);
* Allocate 'size' units from the given map, starting at address 'addr'.
* Return 'addr' if successful, 0 if not.
* This may cause the creation or destruction of a resource map segment.
* This routine will return failure status if there is not enough room
* for a required additional map segment.
* An attempt to use this on 'swapmap' will result in
* a failure return. This is due mainly to laziness and could be fixed
* to do the right thing, although it probably will never be used.
register struct mapent
*ep
= (struct mapent
*)(mp
+1);
register struct mapent
*bp
, *bp2
;
* Look for a map segment containing the requested address.
* If none found, return failure.
for (bp
= ep
; bp
->m_size
; bp
++)
if (bp
->m_addr
<= addr
&& bp
->m_addr
+ bp
->m_size
> addr
)
* If segment is too small, return failure.
* If big enough, allocate the block, compressing or expanding
if (bp
->m_addr
+ bp
->m_size
< addr
+ size
)
if (bp
->m_addr
+ bp
->m_size
== addr
+ size
) {
* Allocate entire segment and compress map
(bp2
-1)->m_addr
= bp2
->m_addr
;
(bp2
-1)->m_size
= bp2
->m_size
;
* Allocate first part of segment
if (bp
->m_addr
+ bp
->m_size
== addr
+ size
) {
* Allocate last part of segment
* Allocate from middle of segment, but only
* if table can be expanded.
for (bp2
=bp
; bp2
->m_size
; bp2
++)
(bp2
+1)->m_addr
= bp2
->m_addr
;
(bp2
+1)->m_size
= bp2
->m_size
;
(bp
+1)->m_addr
= addr
+ size
;
bp
->m_addr
+ bp
->m_size
- (addr
+ size
);
bp
->m_size
= addr
- bp
->m_addr
;