UnsafeFreeList.mesa
Copyright Ó 1992 by Xerox Corporation. All rights reserved.
Created by Christian Jacobi, April 9, 1992 11:48:58 am PDT
Christian Jacobi, April 13, 1992 3:15 pm PDT
"Template module" to handle free-lists of client data blocks.
This is a quite simple task. However, by using an extra module more detailed care is given to this problem then any single user likely would invest. It is probably worth being fast since the garbage collector provides nicer functionality in any case were speed or fragmentation doesn't matter. It is aimed at multi-threaded applications; single threaded applications don't need fancy locking like UnsafeFreeList. This package is not defying garbage collection; quite the opposite is true. Due to garbage collection it makes sense to utilize many but quite short free-lists.
We overwrite the data blocks directly for linking them together in the free list. As this is quite unsafe, we propose that clients of UnsafeFreeList do not export or share the UnsafeFreeList.Context's used.
Typical usage pattern
xFreeList: UnsafeFreeList.Context ~ UnsafeFreeList.NewContext[100];
NewX: PROC [] RETURNS [x: REF X] = TRUSTED {
x ¬ LOOPHOLE[UnsafeFreeList.Get[xFreeList]];
IF x=NIL THEN x ¬ NEW[X]
};
FreeX: PROC [x: REF X] = TRUSTED {
UnsafeFreeList.Free[xFreeList, LOOPHOLE[x]];
};
We also propose to use non-global free lists (to reduce sharing the monitor lock among processors in a multi-processor environment).
UnsafeFreeList:
CEDAR
DEFINITIONS
LOCKS ct USING ct: Context ~
BEGIN
Context:
TYPE =
REF ContextRep;
A context represents one particular free-list.
The context is the unit of mutual exclusion.
ContextRep:
PRIVATE
TYPE =
MONITORED
RECORD [
lim: INT ¬ 0, --counter for how many more elements can be include in list.
first: POINTER TO Block ¬ NIL, --front of list; where elements are removed
last: POINTER TO Block ¬ NIL --tail of list; where new free elements are queued
];
Note that lim is accessed outside the monitor lock, as the exact value doesn't really matter.
Block:
PRIVATE
TYPE =
RECORD [next:
POINTER
TO Block <<and probably more>>];
NewContext:
PUBLIC
PROC [capacity:
INT ¬ 20]
RETURNS [Context] =
INLINE {
Allocates a free-list context willing of holding up to capacity elements
RETURN [NEW[ContextRep ¬ [lim: capacity]]];
};
Free:
PUBLIC
UNSAFE
PROC [ct: Context, ptr:
POINTER] =
TRUSTED
INLINE {
Hangs ptr^ onto the free-list designated by ct
IF ptr#NIL AND ct.lim>0 THEN EntryFree[ct, LOOPHOLE[ptr]]
};
EntryFree:
PRIVATE
ENTRY
PROC [ct: Context, d:
POINTER
TO Block] =
TRUSTED
INLINE {
ct.lim ¬ ct.lim-1;
d.next ¬ NIL;
IF ct.last#NIL THEN ct.last.next ¬ d ELSE ct.first ¬ d;
ct.last ¬ d
};
Get:
PUBLIC
PROC [ct: Context]
RETURNS [
POINTER ¬
NIL] =
TRUSTED INLINE {
Removes and returns an element from free-list, or returns NIL in case the free-list is empty.
We are using first in first out order.
IF ct.first#NIL THEN RETURN [LOOPHOLE[EntryGet[ct]]];
};
EntryGet:
PRIVATE
ENTRY
PROC [ct: Context]
RETURNS [d:
POINTER
TO Block] =
TRUSTED
INLINE {
IF (d ¬ ct.first)#
NIL
THEN {
ct.lim ¬ ct.lim+1;
ct.first ¬ d.next;
IF ct.first=NIL THEN ct.last ¬ NIL;
d.next ¬ NIL;
};
};
FreeCapacity:
PUBLIC
PROC [ct: Context]
RETURNS [
INT] =
INLINE {
Returns approximate number of additional elements the free list is willing to remember.
This is really approximate: there exist race conditions which could make this negative...
RETURN [ct.lim];
};
END.