[b56206a] | 1 | # |
---|
| 2 | # $Id$ |
---|
| 3 | # |
---|
| 4 | |
---|
| 5 | This document explains how the unlimited objects support works. This was |
---|
| 6 | written by Chris Johns <ccj@acm.org> of Objective Design Systems as a |
---|
| 7 | design document. This was submitted as part of the patch which added |
---|
| 8 | this capability. |
---|
| 9 | |
---|
| 10 | Unlimited Local Node Objects |
---|
| 11 | ============================ |
---|
| 12 | |
---|
| 13 | 1. Why ? |
---|
| 14 | |
---|
| 15 | This patch changes the way RTEMS allocates, frees, and manages the |
---|
| 16 | 'Objects_Control' structure. |
---|
| 17 | |
---|
| 18 | The 'Objects_Control' structure is at the root of all objects in |
---|
| 19 | RTEMS. The RTEMS and POSIX API allows users to create tasks, message |
---|
| 20 | queues, semaphores and other resources. These are all a type of |
---|
| 21 | Object. The POSIX API allow similar operations. These also map to |
---|
| 22 | Objects. |
---|
| 23 | |
---|
| 24 | Currently the number of objects that can be created is a static value |
---|
| 25 | loaded into the Configuration table before starting the kernel. The |
---|
| 26 | application cannot exceed these limits. Various means are used to tune |
---|
| 27 | this value. During development the value is usually set large. This |
---|
| 28 | saves having to change it everytime a developer adds a new |
---|
| 29 | resource. With a large team of developers the configuration table file |
---|
| 30 | can cycle through a large number of revisions. The wasted memory is |
---|
| 31 | only recovered when memory runs short. The issue of the configuration |
---|
| 32 | table parameters become more important the less memory you have. |
---|
| 33 | |
---|
| 34 | The Configuration table requires a calculation to occur at compile |
---|
| 35 | time to set the size of the Workspace. The calculation is an |
---|
| 36 | estimate. You need to specify an overhead value for memory that can |
---|
| 37 | not be calculated. An example of memory that cannot be calculated is |
---|
| 38 | stack sizes. This issue is not directly related to allowing unlimited |
---|
| 39 | objects how-ever the need to calculate the memory usage for a system |
---|
| 40 | in this manner is prone to error. |
---|
| 41 | |
---|
| 42 | I would like to see download support added to RTEMS. The kernel |
---|
| 43 | configuration being set at boot time means a download application can |
---|
| 44 | be limited. This can defeat one of the purposes of using downloaded |
---|
| 45 | code, no need to change ROMs. In a system I worked on the cost to |
---|
| 46 | change ROMS in a complete system was high and could take a week. This |
---|
| 47 | change is the first phase of supporting downloaded applications. |
---|
| 48 | |
---|
| 49 | 1.1 How do Objects work ? |
---|
| 50 | |
---|
| 51 | All applications interact with the super core (c/src/exec/score) via |
---|
| 52 | an API. The central structure used in the super core is the |
---|
| 53 | `object'. Two application interfaces exist. They are RTEMS and |
---|
| 54 | POSIX. Both map to the super core using objects. |
---|
| 55 | |
---|
| 56 | An object in RTEMS is a resource which the user (through the API) |
---|
| 57 | creates. The different types of objects are referred to as classes of |
---|
| 58 | objects. An object is referenced by an id. This is of type `rtems_id' |
---|
| 59 | and is a 32bit unsigned integer. The id is unique for each object no |
---|
| 60 | matter what class. |
---|
| 61 | |
---|
| 62 | Objects are anchored by the `_Object_Information' structure. There is |
---|
| 63 | one per type or class of object. A global table of pointers to each |
---|
| 64 | information structure for a class of objects is held in |
---|
| 65 | `Objects_Information_table'. |
---|
| 66 | |
---|
| 67 | Objects consist of 6 main structures. The `_Object_Information' is the |
---|
| 68 | root structure. It contains pointers to the `local_table', |
---|
| 69 | `name_table', `global_table', the Inactive chain, and the object |
---|
| 70 | memory. It also contains the various variables which describe the |
---|
| 71 | object. We are only concerned with the `local_table', `name_table', |
---|
| 72 | Inactive chain, and the object memory to support unlimited objects. |
---|
| 73 | |
---|
| 74 | The `local_table' holds the pointers to open objects. A `local_table |
---|
| 75 | entry which is null is free and the object will be sitting on the |
---|
| 76 | Inactive chain. The index into the table is based on part of the |
---|
| 77 | id. Given an id the you can find the index into the `local_table', and |
---|
| 78 | therefore the object. The `local_table' has the entries for the |
---|
| 79 | indexes below the minimum_id's index. The minimum_id is always set to |
---|
| 80 | 1 (the change allows another value to be selected if require). The |
---|
| 81 | index of 0 is reserved and never used. This allows any actions using |
---|
| 82 | an id of zero to fail or map to a special case. |
---|
| 83 | |
---|
| 84 | The `name_table' holds the names of the objects. Each entry in this |
---|
| 85 | table is the maximum size the name of the object can be. The size of |
---|
| 86 | names is not constrained by the object code (but is by the MP object |
---|
| 87 | code, and the API and should be fixed). |
---|
| 88 | |
---|
| 89 | The `global_table' and code that uses it has not changed. I did not |
---|
| 90 | look at the this code, and I am not farmilar with it. |
---|
| 91 | |
---|
| 92 | The Inactive chain stores objects which are free or not |
---|
| 93 | allocated. This design saves searching for a free object when |
---|
| 94 | allocating therefore providing a deterministic allocation scheme. When |
---|
| 95 | the chain is empty a null is returned. |
---|
| 96 | |
---|
| 97 | The change documented below basically extends the `local_table' and |
---|
| 98 | `name_table' structures at run-time. The memory used be these table |
---|
| 99 | is not large compared to the memory for the objects, and so are never |
---|
| 100 | reduced in size once extended. The object's memory grows and shrinks |
---|
| 101 | depending of the user's usage. |
---|
| 102 | |
---|
| 103 | Currently, the user specifies the total number of objects in the |
---|
| 104 | Configuration table. The change alters the function of the values in |
---|
| 105 | the Configuration table. A flag can be masked on to the value which |
---|
| 106 | selects the extending mode. If the user does not set the flag the |
---|
| 107 | object code operates with an object ceiling. A small performance |
---|
| 108 | overhead will be incurred as the allocate and free routines are now |
---|
| 109 | not inlined and a check of the auto_extend flag is made. The remaining |
---|
| 110 | value field of the Configuration table entry is total number of |
---|
| 111 | objects that can be allocated when not in unlimited mode. |
---|
| 112 | |
---|
| 113 | If the user masks the flag on to a value on the Configuration table |
---|
| 114 | auto-exdending mode is selected for that class of object. The value |
---|
| 115 | becomes the allocation unit size. If there are no free objects the |
---|
| 116 | object's tables are extended by the allocation unit number of |
---|
| 117 | objects. The object table is shrunk when the user frees objects. The |
---|
| 118 | table must have one free allocation block, and at least half the |
---|
| 119 | allocation size of another block before the object memory of the free |
---|
| 120 | allocation block is returned to the heap. This stops threshold |
---|
| 121 | thrashing when objects around the allocation unit size and created and |
---|
| 122 | destroyed. |
---|
| 123 | |
---|
| 124 | At least one allocation block size of objects is created and never |
---|
| 125 | destroyed. |
---|
| 126 | |
---|
| 127 | The change to support unlimited objects has extended the object |
---|
| 128 | information structure. |
---|
| 129 | |
---|
| 130 | The flag, `auto_extend' controls if the object can be automatically |
---|
| 131 | extended. The user masks the flag RTEMS_UNLIMITED_FLAGS onto the |
---|
| 132 | Configuration table number to select the auto-extend mode. This is |
---|
| 133 | passed to the `_Objects_Initialize_information' function in the |
---|
| 134 | parameter maximum. The flag is tested for and the auto_extend flag |
---|
| 135 | updated to reflect the state of the flag before being stipped from the |
---|
| 136 | maximum. |
---|
| 137 | |
---|
| 138 | The `allocation_size' is set to the parameter maxium in the function |
---|
| 139 | `_Objects_Initialize_information' if `auto_extend' is true. Making the |
---|
| 140 | allocation size small causes the memory to be allocated and freed more |
---|
| 141 | often. This only effects the performance times for creating a resource |
---|
| 142 | such as a task. It does how-ever give you fine grain memory |
---|
| 143 | control. If the performance of creating resources is not a problem |
---|
| 144 | make the size small. |
---|
| 145 | |
---|
| 146 | The size of the object is required to be stored. It is used when |
---|
| 147 | extending the object information. |
---|
| 148 | |
---|
| 149 | A count of the object on the Inactive list is maintained. This is used |
---|
| 150 | during freeing objects. If the count is above 1.5 times the |
---|
| 151 | `allocation_size' an attempt is made to shrink the object |
---|
| 152 | informtation. Shrinking might not always succeed as a single |
---|
| 153 | allocation block might not be free. Random freeing of objects can |
---|
| 154 | result in some fragmentation. Any further allocations will use the |
---|
| 155 | free objects before extending the object's information tables. |
---|
| 156 | |
---|
| 157 | A table of inactive objects per block is maintained. This table, like |
---|
| 158 | the `local_table' and `name_table' grows as more blocks are |
---|
| 159 | allocated. A check is made of a blocks inactive count when an object |
---|
| 160 | which is part of that block is freed. If the total inactive count |
---|
| 161 | exceeds 1.5 times the allocation size, and the block's inactive count |
---|
| 162 | is the allocation_size, the objects data block is returnd to the |
---|
| 163 | workspace heap. |
---|
| 164 | |
---|
| 165 | The `objects_blocks' is a table of pointers. The object_block's pointers |
---|
| 166 | point to the object's data block. The object's data block is a single |
---|
| 167 | allocation of the name space and object space. This was two separate |
---|
| 168 | allocations but is now one. The objects_block's table is use to |
---|
| 169 | determine if a block is allocated, and the address of the memory block |
---|
| 170 | to be returned to the workspace heap when the object informtation |
---|
| 171 | space is shrunk. |
---|
| 172 | |
---|
| 173 | 2.0 Detail Of the Auto-Extend Patch to rtems-4.0.0, Snapshot 19990302 |
---|
| 174 | |
---|
| 175 | o Configuration table support. |
---|
| 176 | |
---|
| 177 | Added a flag OBJECTS_UNLIMITED_OBJECTS to score/headers/object.h |
---|
| 178 | header file. This is referenced in the file sapi/headers/config.h to |
---|
| 179 | create the flag RTEMS_UNLIMITED_OBJECTS. A macro is provided to take |
---|
| 180 | a resource count and apply the flag. The macro is called |
---|
| 181 | `rtems_resource_unlimited'. The user uses this macro when building a |
---|
| 182 | configuration table. It can be used with the condefs.h header file. |
---|
| 183 | |
---|
| 184 | o Object Information Structure |
---|
| 185 | |
---|
| 186 | The object information structure, Objects_Information, has been |
---|
| 187 | extended with the follow fields : |
---|
| 188 | |
---|
| 189 | boolean auto_extend - |
---|
| 190 | |
---|
| 191 | When true the object's information tables can be extended untill |
---|
| 192 | all memory is used. When false the current functionallity is |
---|
| 193 | maintained. |
---|
| 194 | |
---|
| 195 | unsigned32 allocation_size - |
---|
| 196 | |
---|
| 197 | When auto_extend is true, it is the value in the Configuration |
---|
| 198 | table and is the number of objects the object's information |
---|
| 199 | tables are extended or shrunk. |
---|
| 200 | |
---|
| 201 | unsigned32 size - |
---|
| 202 | |
---|
| 203 | The size of the object. It is used to calculate the size of |
---|
| 204 | memory required to be allocated when extending the table. |
---|
| 205 | |
---|
| 206 | unsigned32 inactive - |
---|
| 207 | |
---|
| 208 | The number of elements on the Inactive chain. |
---|
| 209 | |
---|
| 210 | unsigned32 *inactive_per_block - |
---|
| 211 | |
---|
| 212 | Pointer to a table of counts of the inactive objects from a |
---|
| 213 | block on the Inactive chain. It is used to know which blocks are |
---|
| 214 | all free and therefore can be returned to the heap. |
---|
| 215 | |
---|
| 216 | void **object_blocks - |
---|
| 217 | |
---|
| 218 | Pointer to a table of pointers to the object data. The table |
---|
| 219 | holds the pointer used to return a block to the heap when |
---|
| 220 | shrinking the object's information tables. |
---|
| 221 | |
---|
| 222 | o Changes to Existing Object Functions |
---|
| 223 | |
---|
| 224 | Two functions prototypes are added. They are : |
---|
| 225 | |
---|
| 226 | _Objects_Extend_information, |
---|
| 227 | _Objects_Shrink_information |
---|
| 228 | _Object_Allocate, and |
---|
| 229 | _Object_Free |
---|
| 230 | |
---|
| 231 | The last were inlined, how-ever now they are not as they are too |
---|
| 232 | complex to implement as macros now. |
---|
| 233 | |
---|
| 234 | o Object Inline and Macro Changes |
---|
| 235 | |
---|
| 236 | The functions : |
---|
| 237 | |
---|
| 238 | _Object_Allocate, and |
---|
| 239 | _Object_Free |
---|
| 240 | |
---|
| 241 | are now not inlined. The function : |
---|
| 242 | |
---|
| 243 | _Objects_Get_local_object, and |
---|
| 244 | _Objects_Set_local_object |
---|
| 245 | |
---|
| 246 | have been added. There was no provided interface to allow an API to |
---|
| 247 | get/set an objects local pointer given an index. The POSIX code |
---|
| 248 | should be updated to use this interface. |
---|
| 249 | |
---|
| 250 | The function : |
---|
| 251 | |
---|
| 252 | _Objects_Get_information |
---|
| 253 | |
---|
| 254 | has been moved to be an inline function. It is used in the get |
---|
| 255 | object call which the API uses for every object reference. |
---|
| 256 | |
---|
| 257 | o Object Initialisation |
---|
| 258 | |
---|
| 259 | The function _Objects_Initialize_information has been changed to |
---|
| 260 | initialisation of the information structure's fields then call the |
---|
| 261 | new function _Objects_Extend_information. |
---|
| 262 | |
---|
| 263 | The first block of objects is always allocated and never |
---|
| 264 | released. This means with the auto-extend flag set to true the user |
---|
| 265 | still sees the same behaviour expected without this change. That is |
---|
| 266 | the number objects specified in the Configuration table is the |
---|
| 267 | number of object allocated during RTEMS initialisation. If not |
---|
| 268 | enough memory is found during this initial extend a fatal error |
---|
| 269 | occurs. The fatal error only occurs for this case of extending the |
---|
| 270 | object's information tables. |
---|
| 271 | |
---|
| 272 | o Object Information Extend |
---|
| 273 | |
---|
| 274 | The _Object_Information_Extend is a new function. It takes some of |
---|
| 275 | the code form the old _Object_Initialize_information function. The |
---|
| 276 | function extends an object's information base. |
---|
| 277 | |
---|
| 278 | Extending the first time is a special case. The function assumes the |
---|
| 279 | maximum index will be less than the minimum index. This means the |
---|
| 280 | minimum index must be greater than 0 at initialisation. The other |
---|
| 281 | special case made is coping the tables from the old location to the |
---|
| 282 | new location. The first block case is trapped and tables are |
---|
| 283 | initialised instead. Workspace allocation for the first block is |
---|
| 284 | tested for an if the first block the allocate or fatal error call is |
---|
| 285 | made. This traps an RTEMS initialise allocation error. |
---|
| 286 | |
---|
| 287 | The remainder of the code deals with all cases of extending the |
---|
| 288 | object's information. |
---|
| 289 | |
---|
| 290 | The current block count is first determined, then a scan of the |
---|
| 291 | object_block table is made to locate a free slot. Blocks can be |
---|
| 292 | freed in any order. The index base for the block is also determined. |
---|
| 293 | |
---|
| 294 | If the index base is greater than the maximum index, the tables must |
---|
| 295 | grow. To grow the tables, a new larger memory block is allocated and |
---|
| 296 | the tables copied. The object's information structure is then |
---|
| 297 | updated to point to the new tables. The tables are allocated in one |
---|
| 298 | memory block from the work-space heap. The single block is then |
---|
| 299 | broken down in the required tables. |
---|
| 300 | |
---|
| 301 | Once the tables are copied, and the new extended parts initialised |
---|
| 302 | the table pointers in the object's information structure are |
---|
| 303 | updated. This is protected by masking interrupts. |
---|
| 304 | |
---|
| 305 | The old table's memory block is returned to the heap. |
---|
| 306 | |
---|
| 307 | The names table and object is allocated. This again is a single |
---|
| 308 | block which is divided. |
---|
| 309 | |
---|
| 310 | The objects are initialised onto a local Inactive chain. They are |
---|
| 311 | then copied to the object's Inactive chain to complete the |
---|
| 312 | initialisation. |
---|
| 313 | |
---|
| 314 | o Object Informtation Shrink |
---|
| 315 | |
---|
| 316 | The _Object_Shrink_information function is new. It is required to |
---|
| 317 | scan all the blocks to see which one has no objects allocated. The |
---|
| 318 | last object freed might not belong to a block which is completely |
---|
| 319 | free. |
---|
| 320 | |
---|
| 321 | Once a block is located, the Inactive chain is interated down |
---|
| 322 | looking for objects which belong to the block of object being |
---|
| 323 | released. |
---|
| 324 | |
---|
| 325 | Once the Inactive chain scan is complete the names table and object |
---|
| 326 | memory is returned to the work-space heap and the table references cleared. |
---|
| 327 | |
---|
| 328 | XXX - I am not sure if this should occur if better protection or |
---|
| 329 | different code to provide better protection. |
---|
| 330 | |
---|
| 331 | The information tables do not change size. Once extended they never |
---|
| 332 | shrink. |
---|
| 333 | |
---|
| 334 | o Object Allocation |
---|
| 335 | |
---|
| 336 | The _Objects_Allocate attempts to get an object from the Inactive |
---|
| 337 | chain. If auto-extend mode is not enabled no further processing |
---|
| 338 | occurs. The extra overhead for this implemetation is the function is |
---|
| 339 | not inlined and check of a boolean occurs. It should effect the |
---|
| 340 | timing figures. |
---|
| 341 | |
---|
| 342 | If auto-extend is enabled, a further check is made to see if the get |
---|
| 343 | from the Inactive chain suceeded in getting an object. If it failed |
---|
| 344 | a call is made to extend the object's information tables. |
---|
| 345 | |
---|
| 346 | The get from the Inactive chain is retried. The result of this is |
---|
| 347 | returned to the user. A failure here is the users problem. |
---|
| 348 | |
---|
| 349 | o Object Free |
---|
| 350 | |
---|
| 351 | The _Objects_Free puts the object back onto the Inactive |
---|
| 352 | chain. Again if auto-extend mode is not enabled no further |
---|
| 353 | processing occurs and performance overhead will low. |
---|
| 354 | |
---|
| 355 | If auto-extend mode is enabled, a check is to see if the number of |
---|
| 356 | Inactive objects is one and a half times the allocation size. If |
---|
| 357 | there are that many free objects an attempt is made to shrink the |
---|
| 358 | object's information. |
---|
| 359 | |
---|
| 360 | o Object Index and the Get Function |
---|
| 361 | |
---|
| 362 | The existing code allocates the number of object specified in the |
---|
| 363 | configuration table, how-ever it makes the local_table have one more |
---|
| 364 | element. This is the slot for an id of 0. The 0 slot is always a |
---|
| 365 | NULL providing a simple check for a 0 id for object classes. |
---|
| 366 | |
---|
| 367 | The existing _Objects_Get code removes the minimum id, which I think |
---|
| 368 | could only be 1 from the index, then adds one for the 0 slot. |
---|
| 369 | |
---|
| 370 | This change removes this index adjustment code in _Objects_Get. |
---|
| 371 | |
---|
| 372 | The extend information starts the index count when scanning for free |
---|
| 373 | blocks at the minumun index. This means the base index for a block |
---|
| 374 | will always be adjusted by the minimum index. The extend information |
---|
| 375 | function only ever allocates the allocation size of |
---|
| 376 | objects. Finially the object's local_table size is the maximum plus |
---|
| 377 | the minumum index size. The maximum is really the maximum index. |
---|
| 378 | |
---|
| 379 | This means the values in the object's information structure and |
---|
| 380 | tables do not need the index adjustments which existed before. |
---|
| 381 | |
---|
| 382 | o The Test |
---|
| 383 | |
---|
| 384 | A new sample test, unlimited is provided. It attempts to test this |
---|
| 385 | change. |
---|
| 386 | |
---|
| 387 | |
---|