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 | |
---|