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