diff options
Diffstat (limited to 'c/src/exec/score/src/Unlimited.txt')
| -rw-r--r-- | c/src/exec/score/src/Unlimited.txt | 387 |
1 files changed, 0 insertions, 387 deletions
diff --git a/c/src/exec/score/src/Unlimited.txt b/c/src/exec/score/src/Unlimited.txt deleted file mode 100644 index 7340fc2dfe..0000000000 --- a/c/src/exec/score/src/Unlimited.txt +++ /dev/null @@ -1,387 +0,0 @@ -# -# $Id$ -# - -This document explains how the unlimited objects support works. This was -written by Chris Johns <ccj@acm.org> of Objective Design Systems as a -design document. This was submitted as part of the patch which added -this capability. - -Unlimited Local Node Objects -============================ - -1. Why ? - -This patch changes the way RTEMS allocates, frees, and manages the -'Objects_Control' structure. - -The 'Objects_Control' structure is at the root of all objects in -RTEMS. The RTEMS and POSIX API allows users to create tasks, message -queues, semaphores and other resources. These are all a type of -Object. The POSIX API allow similar operations. These also map to -Objects. - -Currently the number of objects that can be created is a static value -loaded into the Configuration table before starting the kernel. The -application cannot exceed these limits. Various means are used to tune -this value. During development the value is usually set large. This -saves having to change it everytime a developer adds a new -resource. With a large team of developers the configuration table file -can cycle through a large number of revisions. The wasted memory is -only recovered when memory runs short. The issue of the configuration -table parameters become more important the less memory you have. - -The Configuration table requires a calculation to occur at compile -time to set the size of the Workspace. The calculation is an -estimate. You need to specify an overhead value for memory that can -not be calculated. An example of memory that cannot be calculated is -stack sizes. This issue is not directly related to allowing unlimited -objects how-ever the need to calculate the memory usage for a system -in this manner is prone to error. - -I would like to see download support added to RTEMS. The kernel -configuration being set at boot time means a download application can -be limited. This can defeat one of the purposes of using downloaded -code, no need to change ROMs. In a system I worked on the cost to -change ROMS in a complete system was high and could take a week. This -change is the first phase of supporting downloaded applications. - -1.1 How do Objects work ? - -All applications interact with the super core (c/src/exec/score) via -an API. The central structure used in the super core is the -`object'. Two application interfaces exist. They are RTEMS and -POSIX. Both map to the super core using objects. - -An object in RTEMS is a resource which the user (through the API) -creates. The different types of objects are referred to as classes of -objects. An object is referenced by an id. This is of type `rtems_id' -and is a 32bit unsigned integer. The id is unique for each object no -matter what class. - -Objects are anchored by the `_Object_Information' structure. There is -one per type or class of object. A global table of pointers to each -information structure for a class of objects is held in -`Objects_Information_table'. - -Objects consist of 6 main structures. The `_Object_Information' is the -root structure. It contains pointers to the `local_table', -`name_table', `global_table', the Inactive chain, and the object -memory. It also contains the various variables which describe the -object. We are only concerned with the `local_table', `name_table', -Inactive chain, and the object memory to support unlimited objects. - -The `local_table' holds the pointers to open objects. A `local_table -entry which is null is free and the object will be sitting on the -Inactive chain. The index into the table is based on part of the -id. Given an id the you can find the index into the `local_table', and -therefore the object. The `local_table' has the entries for the -indexes below the minimum_id's index. The minimum_id is always set to -1 (the change allows another value to be selected if require). The -index of 0 is reserved and never used. This allows any actions using -an id of zero to fail or map to a special case. - -The `name_table' holds the names of the objects. Each entry in this -table is the maximum size the name of the object can be. The size of -names is not constrained by the object code (but is by the MP object -code, and the API and should be fixed). - -The `global_table' and code that uses it has not changed. I did not -look at the this code, and I am not farmilar with it. - -The Inactive chain stores objects which are free or not -allocated. This design saves searching for a free object when -allocating therefore providing a deterministic allocation scheme. When -the chain is empty a null is returned. - -The change documented below basically extends the `local_table' and -`name_table' structures at run-time. The memory used be these table -is not large compared to the memory for the objects, and so are never -reduced in size once extended. The object's memory grows and shrinks -depending of the user's usage. - -Currently, the user specifies the total number of objects in the -Configuration table. The change alters the function of the values in -the Configuration table. A flag can be masked on to the value which -selects the extending mode. If the user does not set the flag the -object code operates with an object ceiling. A small performance -overhead will be incurred as the allocate and free routines are now -not inlined and a check of the auto_extend flag is made. The remaining -value field of the Configuration table entry is total number of -objects that can be allocated when not in unlimited mode. - -If the user masks the flag on to a value on the Configuration table -auto-exdending mode is selected for that class of object. The value -becomes the allocation unit size. If there are no free objects the -object's tables are extended by the allocation unit number of -objects. The object table is shrunk when the user frees objects. The -table must have one free allocation block, and at least half the -allocation size of another block before the object memory of the free -allocation block is returned to the heap. This stops threshold -thrashing when objects around the allocation unit size and created and -destroyed. - -At least one allocation block size of objects is created and never -destroyed. - -The change to support unlimited objects has extended the object -information structure. - -The flag, `auto_extend' controls if the object can be automatically -extended. The user masks the flag RTEMS_UNLIMITED_FLAGS onto the -Configuration table number to select the auto-extend mode. This is -passed to the `_Objects_Initialize_information' function in the -parameter maximum. The flag is tested for and the auto_extend flag -updated to reflect the state of the flag before being stipped from the -maximum. - -The `allocation_size' is set to the parameter maxium in the function -`_Objects_Initialize_information' if `auto_extend' is true. Making the -allocation size small causes the memory to be allocated and freed more -often. This only effects the performance times for creating a resource -such as a task. It does how-ever give you fine grain memory -control. If the performance of creating resources is not a problem -make the size small. - -The size of the object is required to be stored. It is used when -extending the object information. - -A count of the object on the Inactive list is maintained. This is used -during freeing objects. If the count is above 1.5 times the -`allocation_size' an attempt is made to shrink the object -informtation. Shrinking might not always succeed as a single -allocation block might not be free. Random freeing of objects can -result in some fragmentation. Any further allocations will use the -free objects before extending the object's information tables. - -A table of inactive objects per block is maintained. This table, like -the `local_table' and `name_table' grows as more blocks are -allocated. A check is made of a blocks inactive count when an object -which is part of that block is freed. If the total inactive count -exceeds 1.5 times the allocation size, and the block's inactive count -is the allocation_size, the objects data block is returnd to the -workspace heap. - -The `objects_blocks' is a table of pointers. The object_block's pointers -point to the object's data block. The object's data block is a single -allocation of the name space and object space. This was two separate -allocations but is now one. The objects_block's table is use to -determine if a block is allocated, and the address of the memory block -to be returned to the workspace heap when the object informtation -space is shrunk. - -2.0 Detail Of the Auto-Extend Patch to rtems-4.0.0, Snapshot 19990302 - -o Configuration table support. - - Added a flag OBJECTS_UNLIMITED_OBJECTS to score/headers/object.h - header file. This is referenced in the file sapi/headers/config.h to - create the flag RTEMS_UNLIMITED_OBJECTS. A macro is provided to take - a resource count and apply the flag. The macro is called - `rtems_resource_unlimited'. The user uses this macro when building a - configuration table. It can be used with the condefs.h header file. - -o Object Information Structure - - The object information structure, Objects_Information, has been - extended with the follow fields : - - boolean auto_extend - - - When true the object's information tables can be extended untill - all memory is used. When false the current functionallity is - maintained. - - unsigned32 allocation_size - - - When auto_extend is true, it is the value in the Configuration - table and is the number of objects the object's information - tables are extended or shrunk. - - unsigned32 size - - - The size of the object. It is used to calculate the size of - memory required to be allocated when extending the table. - - unsigned32 inactive - - - The number of elements on the Inactive chain. - - unsigned32 *inactive_per_block - - - Pointer to a table of counts of the inactive objects from a - block on the Inactive chain. It is used to know which blocks are - all free and therefore can be returned to the heap. - - void **object_blocks - - - Pointer to a table of pointers to the object data. The table - holds the pointer used to return a block to the heap when - shrinking the object's information tables. - -o Changes to Existing Object Functions - - Two functions prototypes are added. They are : - - _Objects_Extend_information, - _Objects_Shrink_information - _Object_Allocate, and - _Object_Free - - The last were inlined, how-ever now they are not as they are too - complex to implement as macros now. - -o Object Inline and Macro Changes - - The functions : - - _Object_Allocate, and - _Object_Free - - are now not inlined. The function : - - _Objects_Get_local_object, and - _Objects_Set_local_object - - have been added. There was no provided interface to allow an API to - get/set an objects local pointer given an index. The POSIX code - should be updated to use this interface. - - The function : - - _Objects_Get_information - - has been moved to be an inline function. It is used in the get - object call which the API uses for every object reference. - -o Object Initialisation - - The function _Objects_Initialize_information has been changed to - initialisation of the information structure's fields then call the - new function _Objects_Extend_information. - - The first block of objects is always allocated and never - released. This means with the auto-extend flag set to true the user - still sees the same behaviour expected without this change. That is - the number objects specified in the Configuration table is the - number of object allocated during RTEMS initialisation. If not - enough memory is found during this initial extend a fatal error - occurs. The fatal error only occurs for this case of extending the - object's information tables. - -o Object Information Extend - - The _Object_Information_Extend is a new function. It takes some of - the code form the old _Object_Initialize_information function. The - function extends an object's information base. - - Extending the first time is a special case. The function assumes the - maximum index will be less than the minimum index. This means the - minimum index must be greater than 0 at initialisation. The other - special case made is coping the tables from the old location to the - new location. The first block case is trapped and tables are - initialised instead. Workspace allocation for the first block is - tested for an if the first block the allocate or fatal error call is - made. This traps an RTEMS initialise allocation error. - - The remainder of the code deals with all cases of extending the - object's information. - - The current block count is first determined, then a scan of the - object_block table is made to locate a free slot. Blocks can be - freed in any order. The index base for the block is also determined. - - If the index base is greater than the maximum index, the tables must - grow. To grow the tables, a new larger memory block is allocated and - the tables copied. The object's information structure is then - updated to point to the new tables. The tables are allocated in one - memory block from the work-space heap. The single block is then - broken down in the required tables. - - Once the tables are copied, and the new extended parts initialised - the table pointers in the object's information structure are - updated. This is protected by masking interrupts. - - The old table's memory block is returned to the heap. - - The names table and object is allocated. This again is a single - block which is divided. - - The objects are initialised onto a local Inactive chain. They are - then copied to the object's Inactive chain to complete the - initialisation. - -o Object Informtation Shrink - - The _Object_Shrink_information function is new. It is required to - scan all the blocks to see which one has no objects allocated. The - last object freed might not belong to a block which is completely - free. - - Once a block is located, the Inactive chain is interated down - looking for objects which belong to the block of object being - released. - - Once the Inactive chain scan is complete the names table and object - memory is returned to the work-space heap and the table references cleared. - - XXX - I am not sure if this should occur if better protection or - different code to provide better protection. - - The information tables do not change size. Once extended they never - shrink. - -o Object Allocation - - The _Objects_Allocate attempts to get an object from the Inactive - chain. If auto-extend mode is not enabled no further processing - occurs. The extra overhead for this implemetation is the function is - not inlined and check of a boolean occurs. It should effect the - timing figures. - - If auto-extend is enabled, a further check is made to see if the get - from the Inactive chain suceeded in getting an object. If it failed - a call is made to extend the object's information tables. - - The get from the Inactive chain is retried. The result of this is - returned to the user. A failure here is the users problem. - -o Object Free - - The _Objects_Free puts the object back onto the Inactive - chain. Again if auto-extend mode is not enabled no further - processing occurs and performance overhead will low. - - If auto-extend mode is enabled, a check is to see if the number of - Inactive objects is one and a half times the allocation size. If - there are that many free objects an attempt is made to shrink the - object's information. - -o Object Index and the Get Function - - The existing code allocates the number of object specified in the - configuration table, how-ever it makes the local_table have one more - element. This is the slot for an id of 0. The 0 slot is always a - NULL providing a simple check for a 0 id for object classes. - - The existing _Objects_Get code removes the minimum id, which I think - could only be 1 from the index, then adds one for the 0 slot. - - This change removes this index adjustment code in _Objects_Get. - - The extend information starts the index count when scanning for free - blocks at the minumun index. This means the base index for a block - will always be adjusted by the minimum index. The extend information - function only ever allocates the allocation size of - objects. Finially the object's local_table size is the maximum plus - the minumum index size. The maximum is really the maximum index. - - This means the values in the object's information structure and - tables do not need the index adjustments which existed before. - -o The Test - - A new sample test, unlimited is provided. It attempts to test this - change. - - |