source: rtems/cpukit/score/src/Unlimited.txt @ b56206a

4.104.114.84.95
Last change on this file since b56206a was b56206a, checked in by Joel Sherrill <joel.sherrill@…>, on 04/19/99 at 17:30:02

Unlimited objects patch design document. Submitted by Chris Johns
<ccj@…> of Objective Design Systems.

  • Property mode set to 100644
File size: 16.2 KB
Line 
1#
2#  $Id$
3#
4
5This document explains how the unlimited objects support works.  This was
6written by Chris Johns <ccj@acm.org> of Objective Design Systems as a
7design document.  This was submitted as part of the patch which added
8this capability. 
9
10Unlimited Local Node Objects
11============================
12
131. Why ?
14
15This patch changes the way RTEMS allocates, frees, and manages the
16'Objects_Control' structure.
17
18The 'Objects_Control' structure is at the root of all objects in
19RTEMS. The RTEMS and POSIX API allows users to create tasks, message
20queues, semaphores and other resources. These are all a type of
21Object. The POSIX API allow similar operations. These also map to
22Objects.
23
24Currently the number of objects that can be created is a static value
25loaded into the Configuration table before starting the kernel. The
26application cannot exceed these limits. Various means are used to tune
27this value. During development the value is usually set large. This
28saves having to change it everytime a developer adds a new
29resource. With a large team of developers the configuration table file
30can cycle through a large number of revisions. The wasted memory is
31only recovered when memory runs short. The issue of the configuration
32table parameters become more important the less memory you have.
33
34The Configuration table requires a calculation to occur at compile
35time to set the size of the Workspace. The calculation is an
36estimate. You need to specify an overhead value for memory that can
37not be calculated. An example of memory that cannot be calculated is
38stack sizes. This issue is not directly related to allowing unlimited
39objects how-ever the need to calculate the memory usage for a system
40in this manner is prone to error.
41
42I would like to see download support added to RTEMS. The kernel
43configuration being set at boot time means a download application can
44be limited. This can defeat one of the purposes of using downloaded
45code, no need to change ROMs. In a system I worked on the cost to
46change ROMS in a complete system was high and could take a week. This
47change is the first phase of supporting downloaded applications.
48
491.1 How do Objects work ?
50
51All applications interact with the super core (c/src/exec/score) via
52an API. The central structure used in the super core is the
53`object'. Two application interfaces exist. They are RTEMS and
54POSIX. Both map to the super core using objects.
55
56An object in RTEMS is a resource which the user (through the API)
57creates. The different types of objects are referred to as classes of
58objects. An object is referenced by an id. This is of type `rtems_id'
59and is a 32bit unsigned integer. The id is unique for each object no
60matter what class.
61
62Objects are anchored by the `_Object_Information' structure. There is
63one per type or class of object. A global table of pointers to each
64information structure for a class of objects is held in
65`Objects_Information_table'.
66
67Objects consist of 6 main structures. The `_Object_Information' is the
68root structure. It contains pointers to the `local_table',
69`name_table', `global_table', the Inactive chain, and the object
70memory. It also contains the various variables which describe the
71object. We are only concerned with the `local_table', `name_table',
72Inactive chain, and the object memory to support unlimited objects.
73
74The `local_table' holds the pointers to open objects. A `local_table
75entry which is null is free and the object will be sitting on the
76Inactive chain. The index into the table is based on part of the
77id. Given an id the you can find the index into the `local_table', and
78therefore the object. The `local_table' has the entries for the
79indexes below the minimum_id's index. The minimum_id is always set to
801 (the change allows another value to be selected if require). The
81index of 0 is reserved and never used. This allows any actions using
82an id of zero to fail or map to a special case.
83
84The `name_table' holds the names of the objects. Each entry in this
85table is the maximum size the name of the object can be. The size of
86names is not constrained by the object code (but is by the MP object
87code, and the API and should be fixed).
88
89The `global_table' and code that uses it has not changed. I did not
90look at the this code, and I am not farmilar with it.
91
92The Inactive chain stores objects which are free or not
93allocated. This design saves searching for a free object when
94allocating therefore providing a deterministic allocation scheme. When
95the chain is empty a null is returned.
96
97The change documented below basically extends the `local_table' and
98`name_table' structures at run-time. The memory used be these table
99is not large compared to the memory for the objects, and so are never
100reduced in size once extended. The object's memory grows and shrinks
101depending of the user's usage.
102
103Currently, the user specifies the total number of objects in the
104Configuration table. The change alters the function of the values in
105the Configuration table. A flag can be masked on to the value which
106selects the extending mode. If the user does not set the flag the
107object code operates with an object ceiling. A small performance
108overhead will be incurred as the allocate and free routines are now
109not inlined and a check of the auto_extend flag is made. The remaining
110value field of the Configuration table entry is total number of
111objects that can be allocated when not in unlimited mode.
112
113If the user masks the flag on to a value on the Configuration table
114auto-exdending mode is selected for that class of object. The value
115becomes the allocation unit size. If there are no free objects the
116object's tables are extended by the allocation unit number of
117objects. The object table is shrunk when the user frees objects. The
118table must have one free allocation block, and at least half the
119allocation size of another block before the object memory of the free
120allocation block is returned to the heap. This stops threshold
121thrashing when objects around the allocation unit size and created and
122destroyed.
123
124At least one allocation block size of objects is created and never
125destroyed.
126
127The change to support unlimited objects has extended the object
128information structure.
129
130The flag, `auto_extend' controls if the object can be automatically
131extended. The user masks the flag RTEMS_UNLIMITED_FLAGS onto the
132Configuration table number to select the auto-extend mode. This is
133passed to the `_Objects_Initialize_information' function in the
134parameter maximum. The flag is tested for and the auto_extend flag
135updated to reflect the state of the flag before being stipped from the
136maximum.
137
138The `allocation_size' is set to the parameter maxium in the function
139`_Objects_Initialize_information' if `auto_extend' is true. Making the
140allocation size small causes the memory to be allocated and freed more
141often. This only effects the performance times for creating a resource
142such as a task. It does how-ever give you fine grain memory
143control. If the performance of creating resources is not a problem
144make the size small.
145
146The size of the object is required to be stored. It is used when
147extending the object information.
148
149A count of the object on the Inactive list is maintained. This is used
150during freeing objects. If the count is above 1.5 times the
151`allocation_size' an attempt is made to shrink the object
152informtation. Shrinking might not always succeed as a single
153allocation block might not be free. Random freeing of objects can
154result in some fragmentation. Any further allocations will use the
155free objects before extending the object's information tables.
156
157A table of inactive objects per block is maintained. This table, like
158the `local_table' and `name_table' grows as more blocks are
159allocated. A check is made of a blocks inactive count when an object
160which is part of that block is freed. If the total inactive count
161exceeds 1.5 times the allocation size, and the block's inactive count
162is the allocation_size, the objects data block is returnd to the
163workspace heap.
164
165The `objects_blocks' is a table of pointers. The object_block's pointers
166point to the object's data block. The object's data block is a single
167allocation of the name space and object space. This was two separate
168allocations but is now one. The objects_block's table is use to
169determine if a block is allocated, and the address of the memory block
170to be returned to the workspace heap when the object informtation
171space is shrunk.
172
1732.0 Detail Of the Auto-Extend Patch to rtems-4.0.0, Snapshot 19990302
174
175o 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
184o 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
222o 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
234o 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
257o 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
272o 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
314o 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
334o 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
349o 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
360o 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
382o The Test
383
384  A new sample test, unlimited is provided. It attempts to test this
385  change.
386
387
Note: See TracBrowser for help on using the repository browser.