[PATCH] add freelist data structure to score

[Sebastian Huber]

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.

>
> 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?

> 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;

> +
> +/**
> + * @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?

> +  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.

> +
> +/**
> + * @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.

[...]

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