[PATCH] add freelist data structure to score
Gedare Bloom
gedare at rtems.org
Mon Jul 15 14:13:25 UTC 2013
Post patch at your convenience. We should include a test case that
uses the workspace. It will also need to do "CONFIGURE_EXTRA_MEMORY"
or something to declare how much of workspace it uses.
On Sun, Jul 14, 2013 at 9:55 PM, Ashi <ashi08104 at gmail.com> wrote:
> Hi, all, I've updated this patch:
> - rename freelist to freechain
> - remove free_count
> - replace freelist_bump() with an user defined extension handle
> - add 2 test cases:
> - spfreechain01: basic freechain operation test
> - spfreechain02: test whether freechain works correctly when calls user
> defined extension handle, and the handle uses malloc for memory allocation.
>
> And I don't whether we need test case for user defined extension handle
> which uses workspace for memory allocation.
>
> Thanks,
> Zhongwei
>
>
> On Fri, Jul 12, 2013 at 6:57 PM, Ashi <ashi08104 at gmail.com> wrote:
>>
>>
>>
>>
>> On Thu, Jul 11, 2013 at 9:18 PM, Gedare Bloom <gedare at rtems.org> wrote:
>>>
>>> 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...
>>
>> OK, I'll use direct way for now.
>>>
>>>
>>> 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
>>> >> >
>>> >
>>> >
>>
>>
>
More information about the devel
mailing list