[PATCH] add freelist data structure to score

Tue Jul 9 12:27:19 UTC 2013

On Mon, Jul 8, 2013 at 11:29 PM, Ashi <ashi08104 at gmail.com> wrote:
> Hi, Sebastian, thanks for your review!
>
> 在 2013-7-7 下午9:49，"Sebastian Huber" <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.
>
I think he means what if someone wants to specify a memory range that
is not managed by a heap or workspace?

>
>>
>>> And the size of new allocated nodes is specified by
>>> user when structure initialization. When initializing, freelist would
>>> pre-allocate a bunch of nodes, which size is also can be specified by
>>> user.
>>>
>>> By the way, the part of motivation of adding this data structure is to
>>> make
>>> RTEMS POSIX Key(this patch will be posted later) unlimited mode more
>>> efficient.
>>>
>>> Thanks,
>>> Zhongwei
>>>
>>>
>>> add_freelist.patch
>>>
>>>
>>> diff --git a/cpukit/score/Makefile.am b/cpukit/score/Makefile.am
>>> index 3f6e686..092d983 100644
>>> --- a/cpukit/score/Makefile.am
>>> +++ b/cpukit/score/Makefile.am
>>> @@ -30,6 +30,7 @@ include_rtems_score_HEADERS +=
>>> include/rtems/score/protectedheap.h
>>>   include_rtems_score_HEADERS += include/rtems/score/interr.h
>>>   include_rtems_score_HEADERS += include/rtems/score/isr.h
>>>   include_rtems_score_HEADERS += include/rtems/score/isrlevel.h
>>> +include_rtems_score_HEADERS += include/rtems/score/freelist.h
>>>   include_rtems_score_HEADERS += include/rtems/score/object.h
>>>   include_rtems_score_HEADERS += include/rtems/score/percpu.h
>>>   include_rtems_score_HEADERS += include/rtems/score/priority.h
>>> @@ -265,6 +266,9 @@ libscore_a_SOURCES += src/pheapallocate.c \
>>>       src/pheapgetblocksize.c src/pheapgetfreeinfo.c src/pheapgetinfo.c \
>>>       src/pheapinit.c src/pheapresizeblock.c src/pheapwalk.c
>>> src/pheapiterate.c
>>>   +## FREELIST_C_FILES
>>> +libscore_a_SOURCES += src/freelist.c
>>> +
>>>   ## RBTREE_C_FILES
>>>   libscore_a_SOURCES += src/rbtree.c \
>>>       src/rbtreeextract.c src/rbtreefind.c src/rbtreefindheader.c \
>>> diff --git a/cpukit/score/include/rtems/score/freelist.h
>>> b/cpukit/score/include/rtems/score/freelist.h
>>> new file mode 100644
>>> index 0000000..c21a872
>>> --- /dev/null
>>> +++ b/cpukit/score/include/rtems/score/freelist.h
>>> @@ -0,0 +1,138 @@
>>> +/**
>>> + * @file
>>> + *
>>> + * @ingroup ScoreFreelist
>>> + *
>>> + * @brief Freelist Handler API
>>> + */
>>> +/*
>>> + * Copyright (c) 2013 Gedare Bloom.
>>> + *
>>> + * The license and distribution terms for this file may be
>>> + * found in the file LICENSE in this distribution or at
>>> + *http://www.rtems.com/license/LICENSE.
>>> + */
>>> +
>>> +#ifndef _FREELIST_H
>>> +#define _FREELIST_H
>>> +
>>> +#include <rtems/score/chain.h>
>>> +#include <rtems/rtems/types.h>
>>> +#include <rtems/score/wkspace.h>
>>> +
>>> +/**
>>> + * @defgroup ScoreFreelist Freelist Handler API
>>> + *
>>> + * @ingroup Score
>>> + *
>>> + * The Freelist Handler is used to manage a chain of nodes, of which
>>> size can
>>> + * automatically increase when there is no free node left. This handler
>>> provides one data structure:
>>> + * Freelist_Control.
>>> + */
>>> +/**@{*/
>>> +
>>> +#ifdef __cplusplus
>>> +extern "C" {
>>> +#endif
>>> +
>>> +/**
>>> + * @typedef Freelist_Control
>>> + */
>>> +typedef struct Freelist_Control_struct Freelist_Control;
>>
>>
>> You can also use
>>
>> typedef struct Freelist_Control Freelist_Control;
>
> OK
>
>
>>
>>> +
>>> +/**
>>> + * @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.
>
I developed this code initially for a free list for interrupt handlers that gets
"bumped" from tasks when the size is too low. So I needed to keep
track of the free nodes remaining. there may be other artifacts left
over from my first implementation. Zhongwei is trying to get the code
into a shape that is usable in score and for supporting keys in
particular.

>
>>
>>> +  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.
>
> Anyway, I'm not sure which kind approach RTEMS prefer.
>
The Extend handler makes pretty good sense, and maybe it can replace
the initialize callout.

We might also consider optimizing the freelist implementation if we
assume that each "bump" allocates contiguous objects. Then the links
between chain nodes can be computed and assigned automatically based
on the size of the node. This automatic setup may be fragile though.

>>
>>> +
>>> +/**
>>> + * @brief Initialize a freelist
>>> + *
>>> + * This routine initializes @a the Freelist_Control structure to manage
>>> a
>>> + * chain of nodes, each node's size is @a node_size and the size of
>>> chain is
>>> + * initialized to @a bump_count and it also will increase with size of
>>> + * @a bump_count. @a callout is called on all the nodes after allocated
>>> from
>>> + * workspace.
>>> + *
>>> + * @param[in] fc is the freelist too initialize.
>>> + * @param[in] node_size is size of the elemment in this freelist.
>>> + * @param[in] bump_count is the size of chain increased when no free
>>> node left.
>>> + * @param[in] callout is the function called on all nodes in
>>> freelist_bump,
>>> + * if it's null, a default function is set.
>>> + * @param[in] use_workspace is used to determine whether heap or
>>> workspace is
>>> + * in for Freelist node.
>>> + */
>>> +void _Freelist_Initialize(
>>> +  Freelist_Control *fc,
>>
>>
>> I would use "freelist" instead of "fc".  Maybe we should use "chain"
>> instead of "list.
>
> Yeah, it's actually a chain of nodes. I don't know whether Gedare have other
> concerns about the name.
>
Chain is fine.

>>
>> [...]
>>
>> --
>> 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.
>>