[PATCH] add freelist data structure to score

[Gedare Bloom]

I don't think we need SAPI. We could consider adding a "classic"
manager interface. Meanwhile, you can write the testsuite with
"#define __RTEMS_VIOLATE_KERNEL_VISIBILITY__" and access the supercore
freelist interface directly...

On Thu, Jul 11, 2013 at 12:25 AM, Ashi <ashi08104 at gmail.com> wrote:
>
> And I'm adding the test case, and find we haven't the SAPI for freelist yet.
> I must add it before adding test case, right?  By the way, is the SAPI same
> as the user-level API layer as Gedare mentioned before? I haven't realized
> it before.
>
>
> On Wed, Jul 10, 2013 at 8:31 PM, Gedare Bloom <gedare at rtems.org> wrote:
>>
>> You would call extend instead of calling bump, or as part of bumping.
>
> Thanks, I see.
>>
>>
>> On Wed, Jul 10, 2013 at 2:30 AM, Ashi <ashi08104 at gmail.com> wrote:
>> > Thanks for all good explanation.
>> >
>> >
>> > On Tue, Jul 9, 2013 at 11:24 PM, Sebastian Huber
>> > <sebastian.huber at embedded-brains.de> wrote:
>> >>
>> >> On 07/09/2013 05:29 AM, Ashi wrote:
>> >>>
>> >>> Hi, Sebastian, thanks for your review!
>> >>>
>> >>> 在 2013-7-7 下午9:49，"Sebastian Huber"
>> >>> <sebastian.huber at embedded-brains.de
>> >>> <mailto:sebastian.huber at embedded-brains.de>>写道：
>> >>>
>> >>>  >
>> >>>  > Hello Ashi,
>> >>>  >
>> >>>  >
>> >>>  > On 06/07/13 09:17, Ashi wrote:
>> >>>  >>
>> >>>  >> Hi all,
>> >>>  >>
>> >>>  >> this patch adds a data structure called freelist to score, there
>> >>> are
>> >>> no
>> >>>  >> test cases yet and should be added later.
>> >>>  >
>> >>>  >
>> >>>  > I would appreciate to have the test for this new stuff included in
>> >>> the
>> >>> patch.
>> >>>
>> >>>
>> >>> sure, I will update the patch with test cases.
>> >>>  >
>> >>>  >
>> >>>  >>
>> >>>  >> Freelist is a structure, which contains a chain of nodes. It
>> >>> supports
>> >>> 2
>> >>>  >> operation:
>> >>>  >> - get node from freelist
>> >>>  >> - put node to freelist.
>> >>>  >> And when there is no enough node in freelist, it will
>> >>> automatically
>> >>>  >> increase itself's size by allocate more nodes from heap or
>> >>> workspace(which
>> >>>  >> is specified by user).
>> >>>  >
>> >>>  >
>> >>>  > What can I do if I like to get the nodes from a magic space?
>> >>>
>> >>>
>> >>> sorry for the unclear, you can get nodes from freelist by 'get'
>> >>> operation. And
>> >>> if you mean get nodes from heap or workspace, it's done by
>> >>> _Freelist_Get_node(), which calls _Freelist_Bump() when there is no
>> >>> free
>> >>> node left.
>> >>
>> >>
>> >> Yes, the problem is that you limit your Freelist to the heap and
>> >> workspace.  If you use a handler function (or virtual method if you
>> >> like)
>> >> then you can avoid this limitation.
>> >>
>> >> [...]
>> >>
>> >>>  >> +/**
>> >>>  >> + * @typedef freelist_callout
>> >>>  >> + */
>> >>>  >> +typedef void (*freelist_callout)(
>> >>>  >> +  Freelist_Control *fc,
>> >>>  >> +  void *nodes
>> >>>  >> +);
>> >>>  >> +
>> >>>  >> +/**
>> >>>  >> + * @typedef Freelist_Control_struct
>> >>>  >> + *
>> >>>  >> + * This is used to manage each element.
>> >>>  >> + */
>> >>>  >> +struct Freelist_Control_struct {
>> >>>  >> +  Chain_Control     Freelist;
>> >>>  >> +  size_t            free_count;
>> >>>  >
>> >>>  >
>> >>>  > Why do we need the free_count?
>> >>>
>> >>> free_count is used to keep track how many nodes there is in freelist.
>> >>> And
>> >>> if
>> >>> free_count is 0 when you try to get node from freelist by call
>> >>> _Freelist_Get_node(), _Freelist_Get_node() will call _Freelist_Bump()
>> >>> to
>> >>> allocate more node from heap or workspace.
>> >>
>> >>
>> >> The list knows if it is empty.  There is not need to store this
>> >> information in two ways.
>> >>
>> >>
>> >>>  >
>> >>>  >> +  size_t            bump_count;
>> >>>  >> +  size_t            node_size;
>> >>>  >
>> >>>  >
>> >>>  >> +  freelist_callout  callout;
>> >>>  >> +  bool              use_workspace;
>> >>>  >> +};
>> >>>  >
>> >>>  >
>> >>>  > I would replace this with an extend handler.
>> >>>  >
>> >>>  > /**
>> >>>  >  * @brief Extends the freelist.
>> >>>  >  *
>> >>>  >  * @param[in] freelist The freelist control.
>> >>>  >  *
>> >>>  >  * @return The count of new nodes.
>> >>>  >  */
>> >>>  > typedef size_t ( *Freelist_Extend )( Freelist_Control *freelist );
>> >>>  >
>> >>>  > This is much more flexible since you only specify the interface and
>> >>> don't
>> >>> limit this to heap/workspace.
>> >>>  >
>> >>>  > You can provide a _Freelist_Extend_with_nothing() which simply
>> >>> returns
>> >>> 0.
>> >>>
>> >>> Yeah, this Freelist_Extend is very flexible, but I feel the
>> >>> Freelist_Extend is
>> >>> a little complex. As it shows in _Freelist_Bump(), if users provides
>> >>> their own
>> >>> extension function, they have to append there new nodes to freelist's
>> >>> internal
>> >>> chain and call their callout function on new nodes. And since
>> >>> _Freelist_Initialize() also would call Freelist_Extend(), if we
>> >>> provided
>> >>> _Freelist_Extend_with_nothing(), the initialization may fail.
>> >>
>> >>
>> >> Since the Freelist_Extend gets the Freelist as a first argument it can
>> >> set
>> >> the extend handler to _Freelist_Extend_with_nothing() after the first
>> >> invocation.
>> >>
>> >> Example:
>> >>
>> >>
>> >> /**
>> >>  * @brief Extends the freelist.
>> >>  *
>> >>  * @param[in] freelist The freelist control.
>> >>  */
>> >> typedef void ( *Freelist_Extend )( Freelist_Control *freelist );
>> >>
>> >> typedef struct {
>> >>   Objects_Control obj;
>> >>   int x;
>> >> } my_obj;
>> >>
>> >> void my_extend( Freelist_Control *freelist )
>> >> {
>> >>   size_t bump_count = freelist->bump_count;
>> >>   size_t size = bump_count * sizeof(my_obj);
>> >>   my_obj *objs = malloc(size);
>> >>
>> >>   _Freelist_Set_extend_handler( freelist, _Freelist_Extend_with_nothing
>> >> );
>> >>   _Chain_Initialize(
>> >>     _Freelist_Get_list( freelist ),
>> >>     objs,
>> >>     bump_count,
>> >>     size
>> >>   );
>> >>
>> >> }
>> >
>> > I'm a little confused by my_extend() function, is it only called after
>> > calling _Freelist_Initialize() by user?
>> >>
>> >>
>> >> [...]
>> >>
>> >> --
>> >> Sebastian Huber, embedded brains GmbH
>> >>
>> >> Address : Dornierstr. 4, D-82178 Puchheim, Germany
>> >> Phone   : +49 89 189 47 41-16
>> >> Fax     : +49 89 189 47 41-09
>> >> E-Mail  : sebastian.huber at embedded-brains.de
>> >> PGP     : Public key available on request.
>> >>
>> >> Diese Nachricht ist keine geschäftliche Mitteilung im Sinne des EHUG.
>> >
>> >
>> > Cheers,
>> > Zhongwei
>> >
>
>