[PATCH] add freelist data structure to score
Gedare Bloom
gedare at rtems.org
Tue Jul 16 14:39:19 UTC 2013
the option you can use is "CONFIGURE_MEMORY_OVERHEAD". It is a "fudge
factor" specified in KiB.
On Mon, Jul 15, 2013 at 11:57 PM, Ashi <ashi08104 at gmail.com> wrote:
> I'm sorry, just forget to attach the patch.
>
>
> On Mon, Jul 15, 2013 at 10:13 PM, Gedare Bloom <gedare at rtems.org> wrote:
>>
>> 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.
>
> Sorry, Gedare, I try to search the "CONFIGURE_EXTRA_MEMORY", but find no
> details.
> I was thinking can we do workspace_allocate() in rtems for user defined data
> structure? Or we have to configure rtems structure as unlimited, like
> regions, semaphores, and then workspace becomes available for user defined
> data structure and we can use workspace_allocate() to allocate user defined
> data.
>
>>
>> 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
>> >>> >> >
>> >>> >
>> >>> >
>> >>
>> >>
>> >
>
> Thanks,
> Zhongwei
More information about the devel
mailing list