[PATCH] add freelist data structure to score
Ashi
ashi08104 at gmail.com
Tue Jul 9 03:29:34 UTC 2013
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.
>
>> 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.
>
>> + 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.
>
>> +
>> +/**
>> + * @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.
>
> [...]
>
> --
> 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.rtems.org/pipermail/devel/attachments/20130709/3f761367/attachment-0001.html>
More information about the devel
mailing list