A range manager tackles the job of fitting as many data items into a limited memory area as it can, and doing so in such a way that when items are freed, fragmentation of the free areas is minimized.
The simple case of a range manager is to manage "1D" ranges. These are ranges that have a start location and use a contiguous, known amount of memory. The more advanced case is a "2D" range manager meant to manage areas of memory that have a width and a height -- however, these areas may have different strides so in effect, a 2D manager manages "dashed lines" of memory.
This may seem simple, but it is not, especially when you add in the fact that several of the memory allocations that the range manager must manage require two or even three levels of memory alignment (it being the case that the range manager is being developed primarily to manage graphics card video RAM.)
The mmutils provides a general purpose 2D range manager. Actually 'general' might not be that true since it is a bit biased by its primary purpose.
So, how does it work? Basically, you define a "range list" which holds the ranges managed by a given area. At first it is empty. To allocate ranges in this area, you first need to define a "request list", populated with the set of candidate ranges that must be allocated. Each range is defined by a set of attributes, mainly its dimensions, and constraints which restrict the way it can be allocated. Then you ask the range manager to find the best fit.
The request list is initialized by a call to rm_list_init(rm_range_list_t ** rl). A range list is defined as follow:
typedef struct rm_range_list { rm_range_t * range; int count; /* number of used ranges */ int allocated; /* number of slots */ } rm_range_list_t;
range points to an array of ranges, and count is the number of ranges currently managed by this list.
Then we need to add ranges to this list. This is done with the rm_list_add(rm_range_list_t * rl, rm_range_t * range) function, which will extend the array in the range list if necessary, and add a new entry by copying the content of range. Let's have look at how to define a range.
typedef struct rm_range_attribute { /* Set by the caller. */ size_t width; size_t height; void * owner; rangeFlags flags; /* These are set by the range manager algorithm. */ size_t start; size_t stride; } rm_range_attribute_t; typedef struct rm_range_constraint { size_t start_min; size_t start_max; size_t start_align; size_t stride_align; } rm_range_constraint_t; typedef struct rm_range { rm_range_attribute_t attribute; rm_range_constraint_t constraint; } rm_range_t;
The attributes are described as follows:
Self-explanatory. These must be set by the caller
This is a user data that can be used to later identify the ressource this range refers to. The range manager don't ever touch it.
The range manager and user communicate through these flags. Part of the bits are written to by the user and read by the range manager, and the other way round.
typedef enum { RANGE_REQUEST_MASK = 0x0000ffff, RANGE_ANSWER_MASK = 0xffff0000, /* user flags, may be OR'd */ /* misc */ RANGE_RELOCATABLE = 0x00000001, /* set if the range can be moved around */ /* constraint */ RANGE_CONSTRAINT_MASK = 0x0000ff00, RANGE_START_MIN = 0x00000100, RANGE_START_MAX = 0x00000200, RANGE_START_ALIGN = 0x00000400, RANGE_STRIDE_ALIGN = 0x00001000, RANGE_STRIDE_FIXED = 0x00002000, /* the stride can't be changed */ /* range manager response */ RANGE_OK_MASK = 0x000f0000, RANGE_ALLOCATED = 0x00010000, /* For newly allocated ranges. */ RANGE_RELOCATED = 0x00020000, /* Existing range has been moved around. */ RANGE_KO_MASK = 0x00f00000, RANGE_INVALID = 0x00100000, /* e.g. start_max < start_min */ RANGE_NO_FIT = 0x00200000, /* Couldn't find a space. */ } rangeFlags;
The user may set any of the bit covered by RANGE_REQUEST_MASK. The other ones will be cleared anyway. The constraint bits must be set for the manager to take them into account. RANGE_STRIDE_FIXED tells the range manager to use the value set in stride as the fixed stride for this range.
Setting these values has no effect, unless the stride is fixed. It is normaly the range manager very purpose to do this.
The following constraints may apply to the range:
The minimum offset where this range may be allocated.
The maximum offest where this range may be allocated. Note that if start_min equals start_max, the range has a fixed starting offset.
This is the alignement factor for the start offset of this range. Setting it to 2 means that the range must be allocated on even address.
This is the alignement factor for the stride of this range.
Example 3.1. A sample request
rm_range_list_t * rm1; rm_range_t r; /* initialize the list */ rm_list_init(&rm1); r.attribute.width=100; r.attribute.height=50; r.constraint.stride_align=17; r.attribute.flags=RANGE_STRIDE_ALIGN; rm_list_add(rm1,&r); r.attribute.width=70; r.attribute.height=20; r.attribute.flags=0; rm_list_add(rm1,&r); r.attribute.width=200; r.attribute.height=20; r.attribute.flags=0; rm_list_add(rm1,&r); r.attribute.width=40; r.attribute.height=30; r.constraint.start_min=0; r.constraint.start_max=0; r.constraint.stride_align=3; r.attribute.flags= RANGE_START_MIN | RANGE_START_MAX | RANGE_STRIDE_ALIGN ; rm_list_add(rm1,&r);
Once the request is ready, rm_list_fit(rm_range_list_t * rl,rm_range_list_t * req, size_t size) is called. It will try to fit the ranges in the request list req into the area managed by the list rl. size is the size of the area managed by rl.
When the call returns, the ranges in req have their attributes altered to reflect the range_manager's choice. The user should loop through the resulting req list and check the RM_RESULT_MASK flags to see which ranges were succesfully placed. For those ranges, start and stride are set.
A set of macros are defined to easily access the attributes of the ranges in a list. Some can only be read.
#define RM_FLAGS(r,i) (r->range[i].attribute.flags) #define RM_SET_FLAGS(r,i,f) (RM_FLAGS(r,i)|=f) #define RM_UNSET_FLAGS(r,i,f) (RM_FLAGS(r,i)&=~f) #define RM_CHECK_ALL_FLAGS(r,i,f) (RM_FLAGS(r,i)&f==f) #define RM_CHECK_FLAGS(r,i,f) (RM_FLAGS(r,i)&f) #define RM_OWNER(r,i) (r->range[i].attribute.owner) #define RM_WIDTH(r,i) (r->range[i].attribute.width) #define RM_HEIGHT(r,i) (r->range[i].attribute.height) #define RM_START(r,i) (r->range[i].attribute.start) #define RM_STRIDE(r,i) (r->range[i].attribute.stride) #define RM_PADDING(r,i) (RM_STRIDE(r,i)-RM_WIDTH(r,i)) #define RM_SURFACE(r,i) (RM_STRIDE(r,i)*RM_HEIGHT(r,i)-RM_PADDING(r,i)) #define RM_END(r,i) (RM_START(r,i) + RM_SURFACE(r,i) - 1) #define RM_CSTR_START_MIN(r,i) (r->range[i].constraint.start_min) #define RM_CSTR_START_MAX(r,i) (r->range[i].constraint.start_max) #define RM_CSTR_START_GAP(r,i) (RM_CSTR_START_MAX(r,i)-RM_CSTR_START_MIN(r,i)) #define RM_CSTR_START_ALIGN(r,i) (r->range[i].constraint.start_align) #define RM_CSTR_STRIDE_ALIGN(r,i) (r->range[i].constraint.stride_align)
Note that the main list rl is not altered by this call. It means that rm_list_fit can be called multiple times with different request lists. When a request list is choosen for allocation, rm_list_alloc(rm_range_list_t * rl, rm_range_list_t * req) is called. The request list must not be changed between the call to rm_range_fit and this one, unless you really know what you are doing. Otherwise, for the believers, the anger of God will fall upon you; for the other ones, your memory might be badly messed up. A harmless operation is to remove a range from a list with rm_list_remove(rm_range_list_t * rl, int idx). This is also the only way to desallocate a range from a managed area.
It is a citizen's duty to collect one's garbage. So don't forget to call rm_list_exit(rm_range_list_t ** rl) on the request lists you don't need.
The range manager is not yet able to shuffle allocated ranges. This will be done by adding ranges to the request list, with owner set to the index of the relocated chunks. This is in my opinion a nice way to tell the user what will actually happen, without touching anything.
Another missing feature is the rm_list_defrag, which would relocated ranges at best to reduce fragmentation after the removal of ranges.
Finally, customizable allocation policy could be introduced.