summary | shortlog | log | commit | commitdiff | tree
raw | patch | inline | side by side (parent: 1c15459)
raw | patch | inline | side by side (parent: 1c15459)
| author | Justin Sobota <jsobota@ti.com> | |
| Mon, 10 Dec 2012 23:55:32 +0000 (18:55 -0500) | ||
| committer | Justin Sobota <jsobota@ti.com> | |
| Mon, 10 Dec 2012 23:55:32 +0000 (18:55 -0500) |
| include/rm_loc.h | patch | blob | history | |
| include/rm_nameserverloc.h | patch | blob | history | |
| include/tree.h | [new file with mode: 0644] | patch | blob |
| rm_services.h | patch | blob | history | |
| src/rm.c | patch | blob | history | |
| src/rm_nameserver.c | patch | blob | history | |
| src/rm_policy.c | patch | blob | history | |
| src/rm_services.c | patch | blob | history | |
| src/rm_transport.c | patch | blob | history |
diff --git a/include/rm_loc.h b/include/rm_loc.h
index bebad4543fee3e30ca5a64394746da9931199bb7..18717972c76af0f180fcaef4c60691ca239fc741 100644 (file)
--- a/include/rm_loc.h
+++ b/include/rm_loc.h
#include <ti/drv/rm/rm_policy.h>
#include <ti/drv/rm/rm_transport.h>
-#if 0
-/* RM permissions structure for CPPI DMA channels and flows */
-typedef struct
-{
- /** Array of pointers to each DMAs channel or flow permissions
- * From CPPI LLD - DMA 0 = SRIO
- * DMA 1 = AIF
- * DMA 2 = FFTC A
- * DMA 3 = FFTC B
- * DMA 4 = PASS
- * DMA 5 = QMSS
- * DMA 6 = FFTC C
- * DMA 7 = BCP
- *
- * Note: Some DMAs may not be supported based on the device */
- Rm_Perms *dmaPermPtrs[RM_CPPI_MAX_DMAS];
-} Rm_CppiChAndFlowPerms;
-
-/* RM Cache Line Alignment Defines and Macros */
-
-#define RM_MAX_CACHE_ALIGN 128 /* Maximum alignment for cache line size */
-
-/* This macro generates compiler error if postulate is false, so
- * allows 0 overhead compile time size check. This "works" when
- * the expression contains sizeof() which otherwise doesn't work
- * with preprocessor */
-#define RM_COMPILE_TIME_SIZE_CHECK(postulate) \
- do { \
- typedef struct { \
- uint8_t NegativeSizeIfPostulateFalse[((int)(postulate))*2 - 1];\
- } PostulateCheck_t; \
- } \
- while (0)
-
-/* Macro to pad out internal permission structures to multiple of RM_MAX_CACHE_ALIGN bytes
- * The macro prevent something else from being placed on same cache line as the permission.
- * arrays. Note that pad[0] is illegal, so must add full RM_MAX_CACHE_ALIGN if structure
- * is already padded by chance. */
-#define RM_ALIGN_PERMISSIONS_ARRAY(numElements, permStructType) ( \
- (((sizeof(permStructType) * (numElements)) % RM_MAX_CACHE_ALIGN) == 0) ? (numElements) : \
- ((numElements) + \
- (RM_MAX_CACHE_ALIGN - \
- ((sizeof(permStructType) * (numElements)) % RM_MAX_CACHE_ALIGN))/sizeof(permStructType)))
-
-/* RM Global Sync Object (unpadded) */
-typedef struct
-{
- /** Rm_init/Rm_start synchronization object. */
- uint8_t globalSyncObj;
-} Rm_Sync_Obj_Unpadded;
-
-/* RM Global Sync Object (padded) */
-typedef struct
-{
- /** Data structure without padding, so sizeof() can compute padding */
- Rm_Sync_Obj_Unpadded obj;
- /** Pad out to end of RM_MAX_CACHE_ALIGN bytes to prevent something else
- * from being placed on same cache line as Rm_Synci_Obj. Note that
- * pad[0] is illegal, so must add full RM_MAX_CACHE_ALIGN if structure
- * is already padded by chance. */
- uint8_t pad[RM_MAX_CACHE_ALIGN -
- (sizeof(Rm_Sync_Obj_Unpadded) % RM_MAX_CACHE_ALIGN)];
-} Rm_Sync_Obj;
-#endif
+/* AVL BBST includes */
+#include <ti/drv/rm/include/tree.h>
+
+/** String stored for resource elements that are not currently allocated to anyone. If the
+ * resource is allocated the allocatedTo field will be populated with the RM instance
+ * name it was allocated to. */
+#define RM_NOT_ALLOCATED_STRING "\0"
/** Maximum size of a transmittable RM policy in bytes */
#define RM_MAX_POLICY_SIZE_BYTES (64) // Placeholder: This will change
Rm_allocatorType_TREE = 1,
} Rm_AllocatorType;
+typedef enum {
+ Rm_allocatorOp_ALLOCATE = 0,
+ Rm_allocatorOp_FREE = 1,
+ Rm_allocatorOp_PRE_ALLOCATE = 2,
+} Rm_AllocatorOp;
+
+typedef struct {
+ char *srcInstName;
+ Rm_AllocatorOp operation;
+ Rm_ResourceInfo *resourceInfo;
+} Rm_AllocatorOpInfo;
+
typedef struct {
uint32_t value;
- bool allocated;
char allocatedTo[RM_INSTANCE_NAME_MAX_CHARS];
} Rm_IntegerEntry;
void Rm_transactionProcessor (Rm_Inst *rmInst, Rm_Transaction *transaction);
+/**********************************************************************
+ ******************* Red-Black Tree BBST Defines **********************
+ **********************************************************************/
+
+/* Declare the tree structure nodes */
+typedef struct _Rm_ResourceTreeNode {
+ RB_ENTRY(_Rm_ResourceTreeNode) linkage;
+ uint32_t base;
+ uint32_t length;
+ char allocatedTo[RM_INSTANCE_NAME_MAX_CHARS];
+} Rm_ResourceTreeNode;
+
+/* Will need to malloc a tree of type Rm_ResourceTree for each tree i want to create */
+/* Declare the tree head structure */
+typedef RB_HEAD(_Rm_ResourceTree, _Rm_ResourceTreeNode) Rm_ResourceTree;
+
+/* Prototype for function that allocates new tree nodes */
+Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength);
+/* Prototype for function that frees new tree nodes */
+void Rm_freeResourceTreeNode(Rm_ResourceTreeNode *treeNode);
+/* Prototype for tree node comparison function
+ * element1 < element2 --> return < 0
+ * element1 = element2 --> return 0
+ * element1 > element2 --> return > 0 */
+int Rm_ResourceTreeNodeCompare(Rm_ResourceTreeNode *element1, Rm_ResourceTreeNode *element2);
+
+/* Generate the tree prototypes */
+RB_PROTOTYPE(_Rm_ResourceTree, _Rm_ResourceTreeNode, linkage, Rm_ResourceTreeNodeCompare);
+
#ifdef __cplusplus
}
#endif
index a8f68c10c6198d3cfab521a7fb0e1408e11674d1..91b5a3bc99ebbb1adb55e77e00b1ad0348af0c99 100644 (file)
/*
- * file rmnameserverloc.h
+ * file rm_nameserverloc.h
*
- * Private data structures of Resource Manager NameServer.
+ * Prototypes and data structures for the Resource Manager NameServer.
*
* ============================================================================
* (C) Copyright 2012, Texas Instruments, Inc.
* \par
*/
-#ifndef RMNAMESERVERLOC_H_
-#define RMNAMESERVERLOC_H_
+#ifndef RM_NAMESERVERLOC_H_
+#define RM_NAMESERVERLOC_H_
#ifdef __cplusplus
extern "C" {
}
#endif
-#endif /* RMNAMESERVERLOC_H_ */
+#endif /* RM_NAMESERVERLOC_H_ */
diff --git a/include/tree.h b/include/tree.h
--- /dev/null
+++ b/include/tree.h
@@ -0,0 +1,748 @@
+/* $OpenBSD: tree.h,v 1.13 2011/07/09 00:19:45 pirofti Exp $ */
+/*
+ * Copyright 2002 Niels Provos <provos@citi.umich.edu>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ * notice, this list of conditions and the following disclaimer in the
+ * documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef _SYS_TREE_H_
+#define _SYS_TREE_H_
+
+/*
+ * This file defines data structures for different types of trees:
+ * splay trees and red-black trees.
+ *
+ * A splay tree is a self-organizing data structure. Every operation
+ * on the tree causes a splay to happen. The splay moves the requested
+ * node to the root of the tree and partly rebalances it.
+ *
+ * This has the benefit that request locality causes faster lookups as
+ * the requested nodes move to the top of the tree. On the other hand,
+ * every lookup causes memory writes.
+ *
+ * The Balance Theorem bounds the total access time for m operations
+ * and n inserts on an initially empty tree as O((m + n)lg n). The
+ * amortized cost for a sequence of m accesses to a splay tree is O(lg n);
+ *
+ * A red-black tree is a binary search tree with the node color as an
+ * extra attribute. It fulfills a set of conditions:
+ * - every search path from the root to a leaf consists of the
+ * same number of black nodes,
+ * - each red node (except for the root) has a black parent,
+ * - each leaf node is black.
+ *
+ * Every operation on a red-black tree is bounded as O(lg n).
+ * The maximum height of a red-black tree is 2lg (n+1).
+ */
+
+#define SPLAY_HEAD(name, type) \
+struct name { \
+ struct type *sph_root; /* root of the tree */ \
+}
+
+#define SPLAY_INITIALIZER(root) \
+ { NULL }
+
+#define SPLAY_INIT(root) do { \
+ (root)->sph_root = NULL; \
+} while (0)
+
+#define SPLAY_ENTRY(type) \
+struct { \
+ struct type *spe_left; /* left element */ \
+ struct type *spe_right; /* right element */ \
+}
+
+#define SPLAY_LEFT(elm, field) (elm)->field.spe_left
+#define SPLAY_RIGHT(elm, field) (elm)->field.spe_right
+#define SPLAY_ROOT(head) (head)->sph_root
+#define SPLAY_EMPTY(head) (SPLAY_ROOT(head) == NULL)
+
+/* SPLAY_ROTATE_{LEFT,RIGHT} expect that tmp hold SPLAY_{RIGHT,LEFT} */
+#define SPLAY_ROTATE_RIGHT(head, tmp, field) do { \
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(tmp, field); \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (0)
+
+#define SPLAY_ROTATE_LEFT(head, tmp, field) do { \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(tmp, field); \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ (head)->sph_root = tmp; \
+} while (0)
+
+#define SPLAY_LINKLEFT(head, tmp, field) do { \
+ SPLAY_LEFT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field); \
+} while (0)
+
+#define SPLAY_LINKRIGHT(head, tmp, field) do { \
+ SPLAY_RIGHT(tmp, field) = (head)->sph_root; \
+ tmp = (head)->sph_root; \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field); \
+} while (0)
+
+#define SPLAY_ASSEMBLE(head, node, left, right, field) do { \
+ SPLAY_RIGHT(left, field) = SPLAY_LEFT((head)->sph_root, field); \
+ SPLAY_LEFT(right, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT((head)->sph_root, field) = SPLAY_RIGHT(node, field); \
+ SPLAY_RIGHT((head)->sph_root, field) = SPLAY_LEFT(node, field); \
+} while (0)
+
+/* Generates prototypes and inline functions */
+
+#define SPLAY_PROTOTYPE(name, type, field, cmp) \
+void name##_SPLAY(struct name *, struct type *); \
+void name##_SPLAY_MINMAX(struct name *, int); \
+struct type *name##_SPLAY_INSERT(struct name *, struct type *); \
+struct type *name##_SPLAY_REMOVE(struct name *, struct type *); \
+ \
+/* Finds the node with the same key as elm */ \
+static __inline struct type * \
+name##_SPLAY_FIND(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) \
+ return(NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) \
+ return (head->sph_root); \
+ return (NULL); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_NEXT(struct name *head, struct type *elm) \
+{ \
+ name##_SPLAY(head, elm); \
+ if (SPLAY_RIGHT(elm, field) != NULL) { \
+ elm = SPLAY_RIGHT(elm, field); \
+ while (SPLAY_LEFT(elm, field) != NULL) { \
+ elm = SPLAY_LEFT(elm, field); \
+ } \
+ } else \
+ elm = NULL; \
+ return (elm); \
+} \
+ \
+static __inline struct type * \
+name##_SPLAY_MIN_MAX(struct name *head, int val) \
+{ \
+ name##_SPLAY_MINMAX(head, val); \
+ return (SPLAY_ROOT(head)); \
+}
+
+/* Main splay operation.
+ * Moves node close to the key of elm to top
+ */
+#define SPLAY_GENERATE(name, type, field, cmp) \
+struct type * \
+name##_SPLAY_INSERT(struct name *head, struct type *elm) \
+{ \
+ if (SPLAY_EMPTY(head)) { \
+ SPLAY_LEFT(elm, field) = SPLAY_RIGHT(elm, field) = NULL; \
+ } else { \
+ int __comp; \
+ name##_SPLAY(head, elm); \
+ __comp = (cmp)(elm, (head)->sph_root); \
+ if(__comp < 0) { \
+ SPLAY_LEFT(elm, field) = SPLAY_LEFT((head)->sph_root, field);\
+ SPLAY_RIGHT(elm, field) = (head)->sph_root; \
+ SPLAY_LEFT((head)->sph_root, field) = NULL; \
+ } else if (__comp > 0) { \
+ SPLAY_RIGHT(elm, field) = SPLAY_RIGHT((head)->sph_root, field);\
+ SPLAY_LEFT(elm, field) = (head)->sph_root; \
+ SPLAY_RIGHT((head)->sph_root, field) = NULL; \
+ } else \
+ return ((head)->sph_root); \
+ } \
+ (head)->sph_root = (elm); \
+ return (NULL); \
+} \
+ \
+struct type * \
+name##_SPLAY_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__tmp; \
+ if (SPLAY_EMPTY(head)) \
+ return (NULL); \
+ name##_SPLAY(head, elm); \
+ if ((cmp)(elm, (head)->sph_root) == 0) { \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL) { \
+ (head)->sph_root = SPLAY_RIGHT((head)->sph_root, field);\
+ } else { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ (head)->sph_root = SPLAY_LEFT((head)->sph_root, field);\
+ name##_SPLAY(head, elm); \
+ SPLAY_RIGHT((head)->sph_root, field) = __tmp; \
+ } \
+ return (elm); \
+ } \
+ return (NULL); \
+} \
+ \
+void \
+name##_SPLAY(struct name *head, struct type *elm) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+ int __comp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while ((__comp = (cmp)(elm, (head)->sph_root))) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if ((cmp)(elm, __tmp) > 0){ \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+} \
+ \
+/* Splay with either the minimum or the maximum element \
+ * Used to find minimum or maximum element in tree. \
+ */ \
+void name##_SPLAY_MINMAX(struct name *head, int __comp) \
+{ \
+ struct type __node, *__left, *__right, *__tmp; \
+\
+ SPLAY_LEFT(&__node, field) = SPLAY_RIGHT(&__node, field) = NULL;\
+ __left = __right = &__node; \
+\
+ while (1) { \
+ if (__comp < 0) { \
+ __tmp = SPLAY_LEFT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp < 0){ \
+ SPLAY_ROTATE_RIGHT(head, __tmp, field); \
+ if (SPLAY_LEFT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKLEFT(head, __right, field); \
+ } else if (__comp > 0) { \
+ __tmp = SPLAY_RIGHT((head)->sph_root, field); \
+ if (__tmp == NULL) \
+ break; \
+ if (__comp > 0) { \
+ SPLAY_ROTATE_LEFT(head, __tmp, field); \
+ if (SPLAY_RIGHT((head)->sph_root, field) == NULL)\
+ break; \
+ } \
+ SPLAY_LINKRIGHT(head, __left, field); \
+ } \
+ } \
+ SPLAY_ASSEMBLE(head, &__node, __left, __right, field); \
+}
+
+#define SPLAY_NEGINF -1
+#define SPLAY_INF 1
+
+#define SPLAY_INSERT(name, x, y) name##_SPLAY_INSERT(x, y)
+#define SPLAY_REMOVE(name, x, y) name##_SPLAY_REMOVE(x, y)
+#define SPLAY_FIND(name, x, y) name##_SPLAY_FIND(x, y)
+#define SPLAY_NEXT(name, x, y) name##_SPLAY_NEXT(x, y)
+#define SPLAY_MIN(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_NEGINF))
+#define SPLAY_MAX(name, x) (SPLAY_EMPTY(x) ? NULL \
+ : name##_SPLAY_MIN_MAX(x, SPLAY_INF))
+
+#define SPLAY_FOREACH(x, name, head) \
+ for ((x) = SPLAY_MIN(name, head); \
+ (x) != NULL; \
+ (x) = SPLAY_NEXT(name, head, x))
+
+/* Macros that define a red-black tree */
+#define RB_HEAD(name, type) \
+struct name { \
+ struct type *rbh_root; /* root of the tree */ \
+}
+
+#define RB_INITIALIZER(root) \
+ { NULL }
+
+#define RB_INIT(root) do { \
+ (root)->rbh_root = NULL; \
+} while (0)
+
+#define RB_BLACK 0
+#define RB_RED 1
+#define RB_ENTRY(type) \
+struct { \
+ struct type *rbe_left; /* left element */ \
+ struct type *rbe_right; /* right element */ \
+ struct type *rbe_parent; /* parent element */ \
+ int rbe_color; /* node color */ \
+}
+
+#define RB_LEFT(elm, field) (elm)->field.rbe_left
+#define RB_RIGHT(elm, field) (elm)->field.rbe_right
+#define RB_PARENT(elm, field) (elm)->field.rbe_parent
+#define RB_COLOR(elm, field) (elm)->field.rbe_color
+#define RB_ROOT(head) (head)->rbh_root
+#define RB_EMPTY(head) (RB_ROOT(head) == NULL)
+
+#define RB_SET(elm, parent, field) do { \
+ RB_PARENT(elm, field) = parent; \
+ RB_LEFT(elm, field) = RB_RIGHT(elm, field) = NULL; \
+ RB_COLOR(elm, field) = RB_RED; \
+} while (0)
+
+#define RB_SET_BLACKRED(black, red, field) do { \
+ RB_COLOR(black, field) = RB_BLACK; \
+ RB_COLOR(red, field) = RB_RED; \
+} while (0)
+
+#ifndef RB_AUGMENT
+#define RB_AUGMENT(x) do {} while (0)
+#endif
+
+#define RB_ROTATE_LEFT(head, elm, tmp, field) do { \
+ (tmp) = RB_RIGHT(elm, field); \
+ if ((RB_RIGHT(elm, field) = RB_LEFT(tmp, field))) { \
+ RB_PARENT(RB_LEFT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_LEFT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (0)
+
+#define RB_ROTATE_RIGHT(head, elm, tmp, field) do { \
+ (tmp) = RB_LEFT(elm, field); \
+ if ((RB_LEFT(elm, field) = RB_RIGHT(tmp, field))) { \
+ RB_PARENT(RB_RIGHT(tmp, field), field) = (elm); \
+ } \
+ RB_AUGMENT(elm); \
+ if ((RB_PARENT(tmp, field) = RB_PARENT(elm, field))) { \
+ if ((elm) == RB_LEFT(RB_PARENT(elm, field), field)) \
+ RB_LEFT(RB_PARENT(elm, field), field) = (tmp); \
+ else \
+ RB_RIGHT(RB_PARENT(elm, field), field) = (tmp); \
+ } else \
+ (head)->rbh_root = (tmp); \
+ RB_RIGHT(tmp, field) = (elm); \
+ RB_PARENT(elm, field) = (tmp); \
+ RB_AUGMENT(tmp); \
+ if ((RB_PARENT(tmp, field))) \
+ RB_AUGMENT(RB_PARENT(tmp, field)); \
+} while (0)
+
+/* Generates prototypes and inline functions */
+#define RB_PROTOTYPE(name, type, field, cmp) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp,)
+#define RB_PROTOTYPE_STATIC(name, type, field, cmp) \
+ RB_PROTOTYPE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
+#define RB_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+attr void name##_RB_INSERT_COLOR(struct name *, struct type *); \
+attr void name##_RB_REMOVE_COLOR(struct name *, struct type *, struct type *);\
+attr struct type *name##_RB_REMOVE(struct name *, struct type *); \
+attr struct type *name##_RB_INSERT(struct name *, struct type *); \
+attr struct type *name##_RB_FIND(struct name *, struct type *); \
+attr struct type *name##_RB_NFIND(struct name *, struct type *); \
+attr struct type *name##_RB_NEXT(struct type *); \
+attr struct type *name##_RB_PREV(struct type *); \
+attr struct type *name##_RB_MINMAX(struct name *, int); \
+ \
+
+/* Main rb operation.
+ * Moves node close to the key of elm to top
+ */
+#define RB_GENERATE(name, type, field, cmp) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp,)
+#define RB_GENERATE_STATIC(name, type, field, cmp) \
+ RB_GENERATE_INTERNAL(name, type, field, cmp, __attribute__((__unused__)) static)
+#define RB_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+attr void \
+name##_RB_INSERT_COLOR(struct name *head, struct type *elm) \
+{ \
+ struct type *parent, *gparent, *tmp; \
+ while ((parent = RB_PARENT(elm, field)) && \
+ RB_COLOR(parent, field) == RB_RED) { \
+ gparent = RB_PARENT(parent, field); \
+ if (parent == RB_LEFT(gparent, field)) { \
+ tmp = RB_RIGHT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_RIGHT(parent, field) == elm) { \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_RIGHT(head, gparent, tmp, field); \
+ } else { \
+ tmp = RB_LEFT(gparent, field); \
+ if (tmp && RB_COLOR(tmp, field) == RB_RED) { \
+ RB_COLOR(tmp, field) = RB_BLACK; \
+ RB_SET_BLACKRED(parent, gparent, field);\
+ elm = gparent; \
+ continue; \
+ } \
+ if (RB_LEFT(parent, field) == elm) { \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = parent; \
+ parent = elm; \
+ elm = tmp; \
+ } \
+ RB_SET_BLACKRED(parent, gparent, field); \
+ RB_ROTATE_LEFT(head, gparent, tmp, field); \
+ } \
+ } \
+ RB_COLOR(head->rbh_root, field) = RB_BLACK; \
+} \
+ \
+attr void \
+name##_RB_REMOVE_COLOR(struct name *head, struct type *parent, struct type *elm) \
+{ \
+ struct type *tmp; \
+ while ((elm == NULL || RB_COLOR(elm, field) == RB_BLACK) && \
+ elm != RB_ROOT(head)) { \
+ if (RB_LEFT(parent, field) == elm) { \
+ tmp = RB_RIGHT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK) {\
+ struct type *oleft; \
+ if ((oleft = RB_LEFT(tmp, field)))\
+ RB_COLOR(oleft, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_RIGHT(head, tmp, oleft, field);\
+ tmp = RB_RIGHT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_RIGHT(tmp, field)) \
+ RB_COLOR(RB_RIGHT(tmp, field), field) = RB_BLACK;\
+ RB_ROTATE_LEFT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } else { \
+ tmp = RB_LEFT(parent, field); \
+ if (RB_COLOR(tmp, field) == RB_RED) { \
+ RB_SET_BLACKRED(tmp, parent, field); \
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ if ((RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) &&\
+ (RB_RIGHT(tmp, field) == NULL || \
+ RB_COLOR(RB_RIGHT(tmp, field), field) == RB_BLACK)) {\
+ RB_COLOR(tmp, field) = RB_RED; \
+ elm = parent; \
+ parent = RB_PARENT(elm, field); \
+ } else { \
+ if (RB_LEFT(tmp, field) == NULL || \
+ RB_COLOR(RB_LEFT(tmp, field), field) == RB_BLACK) {\
+ struct type *oright; \
+ if ((oright = RB_RIGHT(tmp, field)))\
+ RB_COLOR(oright, field) = RB_BLACK;\
+ RB_COLOR(tmp, field) = RB_RED; \
+ RB_ROTATE_LEFT(head, tmp, oright, field);\
+ tmp = RB_LEFT(parent, field); \
+ } \
+ RB_COLOR(tmp, field) = RB_COLOR(parent, field);\
+ RB_COLOR(parent, field) = RB_BLACK; \
+ if (RB_LEFT(tmp, field)) \
+ RB_COLOR(RB_LEFT(tmp, field), field) = RB_BLACK;\
+ RB_ROTATE_RIGHT(head, parent, tmp, field);\
+ elm = RB_ROOT(head); \
+ break; \
+ } \
+ } \
+ } \
+ if (elm) \
+ RB_COLOR(elm, field) = RB_BLACK; \
+} \
+ \
+attr struct type * \
+name##_RB_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *child, *parent, *old = elm; \
+ int color; \
+ if (RB_LEFT(elm, field) == NULL) \
+ child = RB_RIGHT(elm, field); \
+ else if (RB_RIGHT(elm, field) == NULL) \
+ child = RB_LEFT(elm, field); \
+ else { \
+ struct type *left; \
+ elm = RB_RIGHT(elm, field); \
+ while ((left = RB_LEFT(elm, field))) \
+ elm = left; \
+ child = RB_RIGHT(elm, field); \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+ if (RB_PARENT(elm, field) == old) \
+ parent = elm; \
+ (elm)->field = (old)->field; \
+ if (RB_PARENT(old, field)) { \
+ if (RB_LEFT(RB_PARENT(old, field), field) == old)\
+ RB_LEFT(RB_PARENT(old, field), field) = elm;\
+ else \
+ RB_RIGHT(RB_PARENT(old, field), field) = elm;\
+ RB_AUGMENT(RB_PARENT(old, field)); \
+ } else \
+ RB_ROOT(head) = elm; \
+ RB_PARENT(RB_LEFT(old, field), field) = elm; \
+ if (RB_RIGHT(old, field)) \
+ RB_PARENT(RB_RIGHT(old, field), field) = elm; \
+ if (parent) { \
+ left = parent; \
+ do { \
+ RB_AUGMENT(left); \
+ } while ((left = RB_PARENT(left, field))); \
+ } \
+ goto color; \
+ } \
+ parent = RB_PARENT(elm, field); \
+ color = RB_COLOR(elm, field); \
+ if (child) \
+ RB_PARENT(child, field) = parent; \
+ if (parent) { \
+ if (RB_LEFT(parent, field) == elm) \
+ RB_LEFT(parent, field) = child; \
+ else \
+ RB_RIGHT(parent, field) = child; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = child; \
+color: \
+ if (color == RB_BLACK) \
+ name##_RB_REMOVE_COLOR(head, parent, child); \
+ return (old); \
+} \
+ \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_RB_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp; \
+ struct type *parent = NULL; \
+ int comp = 0; \
+ tmp = RB_ROOT(head); \
+ while (tmp) { \
+ parent = tmp; \
+ comp = (cmp)(elm, parent); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ RB_SET(elm, parent, field); \
+ if (parent != NULL) { \
+ if (comp < 0) \
+ RB_LEFT(parent, field) = elm; \
+ else \
+ RB_RIGHT(parent, field) = elm; \
+ RB_AUGMENT(parent); \
+ } else \
+ RB_ROOT(head) = elm; \
+ name##_RB_INSERT_COLOR(head, elm); \
+ return (NULL); \
+} \
+ \
+/* Finds the node with the same key as elm */ \
+attr struct type * \
+name##_RB_FIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (NULL); \
+} \
+ \
+/* Finds the first node greater than or equal to the search key */ \
+attr struct type * \
+name##_RB_NFIND(struct name *head, struct type *elm) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *res = NULL; \
+ int comp; \
+ while (tmp) { \
+ comp = cmp(elm, tmp); \
+ if (comp < 0) { \
+ res = tmp; \
+ tmp = RB_LEFT(tmp, field); \
+ } \
+ else if (comp > 0) \
+ tmp = RB_RIGHT(tmp, field); \
+ else \
+ return (tmp); \
+ } \
+ return (res); \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_NEXT(struct type *elm) \
+{ \
+ if (RB_RIGHT(elm, field)) { \
+ elm = RB_RIGHT(elm, field); \
+ while (RB_LEFT(elm, field)) \
+ elm = RB_LEFT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+} \
+ \
+/* ARGSUSED */ \
+attr struct type * \
+name##_RB_PREV(struct type *elm) \
+{ \
+ if (RB_LEFT(elm, field)) { \
+ elm = RB_LEFT(elm, field); \
+ while (RB_RIGHT(elm, field)) \
+ elm = RB_RIGHT(elm, field); \
+ } else { \
+ if (RB_PARENT(elm, field) && \
+ (elm == RB_RIGHT(RB_PARENT(elm, field), field))) \
+ elm = RB_PARENT(elm, field); \
+ else { \
+ while (RB_PARENT(elm, field) && \
+ (elm == RB_LEFT(RB_PARENT(elm, field), field)))\
+ elm = RB_PARENT(elm, field); \
+ elm = RB_PARENT(elm, field); \
+ } \
+ } \
+ return (elm); \
+} \
+ \
+attr struct type * \
+name##_RB_MINMAX(struct name *head, int val) \
+{ \
+ struct type *tmp = RB_ROOT(head); \
+ struct type *parent = NULL; \
+ while (tmp) { \
+ parent = tmp; \
+ if (val < 0) \
+ tmp = RB_LEFT(tmp, field); \
+ else \
+ tmp = RB_RIGHT(tmp, field); \
+ } \
+ return (parent); \
+}
+
+#define RB_NEGINF -1
+#define RB_INF 1
+
+#define RB_INSERT(name, x, y) name##_RB_INSERT(x, y)
+#define RB_REMOVE(name, x, y) name##_RB_REMOVE(x, y)
+#define RB_FIND(name, x, y) name##_RB_FIND(x, y)
+#define RB_NFIND(name, x, y) name##_RB_NFIND(x, y)
+#define RB_NEXT(name, x, y) name##_RB_NEXT(y)
+#define RB_PREV(name, x, y) name##_RB_PREV(y)
+#define RB_MIN(name, x) name##_RB_MINMAX(x, RB_NEGINF)
+#define RB_MAX(name, x) name##_RB_MINMAX(x, RB_INF)
+
+#define RB_FOREACH(x, name, head) \
+ for ((x) = RB_MIN(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_NEXT(x))
+
+#define RB_FOREACH_SAFE(x, name, head, y) \
+ for ((x) = RB_MIN(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_NEXT(x), 1); \
+ (x) = (y))
+
+#define RB_FOREACH_REVERSE(x, name, head) \
+ for ((x) = RB_MAX(name, head); \
+ (x) != NULL; \
+ (x) = name##_RB_PREV(x))
+
+#define RB_FOREACH_REVERSE_SAFE(x, name, head, y) \
+ for ((x) = RB_MAX(name, head); \
+ ((x) != NULL) && ((y) = name##_RB_PREV(x), 1); \
+ (x) = (y))
+
+#endif /* _SYS_TREE_H_ */
diff --git a/rm_services.h b/rm_services.h
index 15904bc60d13ba09832321fddb7bd031ebfd86c1..f9914adbeaad9206c4f98fbf5f9ae2f1eaaefca5 100644 (file)
--- a/rm_services.h
+++ b/rm_services.h
#define RM_SERVICE_PROCESSING (RM_SERVICE_STATE_BASE+1)
/** RM service was approved. The resource data in the response is valid if
* the service has been approved. */
-#define RM_SERVICE_APPROVED (RM_SERVICE_STATE_BASE+2)
+#define RM_SERVICE_APPROVED_AND_COMPLETED (RM_SERVICE_STATE_BASE+2)
/** Beginning of resource denied reasons */
#define RM_SERVICE_DENIED_BEGIN (RM_SERVICE_STATE_BASE+3)
+/** RM could not find an allocator for the resource specified with the provided name */
+#define RM_SERVICE_DENIED_RESOURCE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN)
+/** A resource value within the specifed base+range could not be found within the resource's
+ * allocator. No action was taken on the resources. */
+#define RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST (RM_SERVICE_DENIED_BEGIN+1)
+/** A resource value within the specifed base+range was not allocated to the RM instance
+ * that is the source of the request. No action was taken on the resources. */
+#define RM_SERVICE_DENIED_RESOURCE_NOT_ALLOCATED_TO_INSTANCE_REQUESTING_THE_SERVICE (RM_SERVICE_DENIED_BEGIN+2)
+/** A resource value within the specifed base+range is already free */
+#define RM_SERVICE_DENIED_RESOURCE_ALREADY_FREE (RM_SERVICE_DENIED_BEGIN+3)
+/** A resource value within the specifed base+range is already allocated to another
+ * RM instance. */
+#define RM_SERVICE_DENIED_RESOURCE_ALREADY_ALLOCATED (RM_SERVICE_DENIED_BEGIN+4)
/** End of resource denied reasons */
-#define RM_SERVICE_DENIED_END (RM_SERVICE_STATE_BASE+3)
+#define RM_SERVICE_DENIED_END (RM_SERVICE_DENIED_BEGIN+4)
/** RM Service Request Error Code Base */
#define RM_SERVICE_ERROR_BASE (-64)
/** Invalid NameServer object modification on non-Server instance */
#define RM_SERVICE_ERROR_NAMESERVER_OBJECT_MOD_ON_INVALID_INSTANCE (RM_SERVICE_ERROR_BASE-12)
+
/**
* @brief Maximum number of characters in the resource names
*/
diff --git a/src/rm.c b/src/rm.c
index 64a9dafa2025076d5dcf36341d9835d33e25be30..16b3dd72ebab462338aba2d5934295e6f44de774 100644 (file)
--- a/src/rm.c
+++ b/src/rm.c
/* RM LIBFDT includes */\r
#include <ti/drv/rm/src/libfdt/libfdt.h>\r
\r
+/* AVL BBST includes */\r
+#include <ti/drv/rm/include/tree.h>\r
+\r
/* RM OSAL layer */\r
#include <rm_osal.h>\r
\r
/**********************************************************************\r
************************** Globals ***********************************\r
**********************************************************************/\r
-#if 0\r
-/* Place QMSS PDSP permissions array */\r
-#pragma DATA_SECTION (rmQmssPdspFirmwarePerms, ".rm");\r
-#pragma DATA_ALIGN (rmQmssPdspFirmwarePerms, 128)\r
-Rm_Perms rmQmssPdspFirmwarePerms[RM_ALIGN_PERMISSIONS_ARRAY(RM_QMSS_FIRMWARE_PDSPS, Rm_Perms)];\r
-#endif\r
-\r
char rmIntegerAllocator[] = "integer";\r
char rmTreeAllocator[] = "tree";\r
\r
/** @brief Global Variable which describes the RM Version Information */\r
const char rmVersionStr[] = RM_VERSION_STR ":" __DATE__ ":" __TIME__;\r
\r
+/**********************************************************************\r
+ ************** Red-Black BBST Tree Allocator Functions ***************\r
+ **********************************************************************/\r
+\r
+/* TODO: This needed? */\r
+/* Prototype for function that allocates new tree nodes */\r
+Rm_ResourceTreeNode *Rm_newResourceTreeNode(uint32_t resourceBase, uint32_t resourceLength)\r
+{\r
+ Rm_ResourceTreeNode *newNode = NULL;\r
+\r
+ newNode = Rm_osalMalloc(sizeof(Rm_ResourceTreeNode));\r
+\r
+ /* Populate the RM relevant fields */\r
+ newNode->base = resourceBase;\r
+ newNode->length = resourceLength;\r
+\r
+ return(newNode);\r
+}\r
+\r
+/* TODO: This needed? */\r
+/* Prototype for function that frees new tree nodes */\r
+void Rm_freeResourceTreeNode(Rm_ResourceTreeNode *treeNode)\r
+{\r
+ /* Free the memory associated with the tree node. */\r
+ Rm_osalFree((void *)treeNode, sizeof(Rm_ResourceTreeNode));\r
+}\r
+\r
+/* Prototype for tree node comparison function\r
+ * element1 < element2 --> return < 0\r
+ * element1 = element2 --> return 0\r
+ * element1 > element2 --> return > 0 */\r
+int Rm_ResourceTreeNodeCompare(Rm_ResourceTreeNode *element1, Rm_ResourceTreeNode *element2)\r
+{\r
+ uint32_t element1End = element1->base + element1->length - 1;\r
+ uint32_t element2End = element2->base + element2->length - 1;\r
+\r
+ if (element1End < element2->base)\r
+ {\r
+ /* End of element1 range is less than the start of element2's range. Return a negative\r
+ * value */\r
+ return (-1);\r
+ }\r
+ else if (element1->base > element2End)\r
+ {\r
+ /* Start of element1 range is after end of element2's range. Return a positive value */\r
+ return (1);\r
+ }\r
+ else\r
+ {\r
+ /* If neither of the latter conditions were satisfied there is some overlap between\r
+ * element1 and element2. Return 0 since the application must handle this overlap. */\r
+ return (0);\r
+ }\r
+}\r
+\r
+/* Generate the red-black tree manipulation functions */\r
+RB_GENERATE(_Rm_ResourceTree, _Rm_ResourceTreeNode, linkage, Rm_ResourceTreeNodeCompare);\r
+\r
/**********************************************************************\r
********************** Internal Functions ****************************\r
**********************************************************************/\r
@@ -356,6 +410,30 @@ Rm_Allocator *Rm_allocatorAdd(Rm_Inst *rmInst, const char *resourceName, Rm_Allo
return (newAllocator);\r
}\r
\r
+Rm_Allocator *Rm_allocatorFind(Rm_Inst *rmInst, char *resourceName)\r
+{\r
+ Rm_Allocator *allocator = (Rm_Allocator *)rmInst->allocators;\r
+\r
+ /* Make sure there is at least one allocator in the allocator list */\r
+ if (allocator != NULL)\r
+ {\r
+ /* Find the resource name within the allocator list. If the end of the\r
+ * allocator list is reached without finding the resource name the \r
+ * allocator pointer will be NULL */\r
+ while (allocator != NULL)\r
+ {\r
+ if (strcmp(allocator->resourceName, resourceName) == 0)\r
+ {\r
+ /* Match: break out of loop and return the allocator */\r
+ break; \r
+ }\r
+ allocator = allocator->nextAllocator;\r
+ }\r
+ }\r
+\r
+ return (allocator);\r
+}\r
+\r
int32_t Rm_allocatorDelete(Rm_Inst *rmInst, char *resourceName)\r
{\r
Rm_Allocator *allocator = (Rm_Allocator *) rmInst->allocators;\r
@@ -447,6 +525,8 @@ int32_t Rm_createIntegerAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_
for (i = range->base; i < (range->base + range->length); i++, entryIndex++)\r
{\r
intRootEntry->resourceArrayBase[entryIndex].value = i;\r
+ /* Initialize the allocatedTo field to the NOT_ALLOCATED string */\r
+ strcpy(intRootEntry->resourceArrayBase[entryIndex].allocatedTo, RM_NOT_ALLOCATED_STRING);\r
}\r
\r
range = range->nextRange;\r
@@ -465,6 +545,66 @@ int32_t Rm_createIntegerAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_
return(0); /* TODO: FIX THIS RETURN */\r
}\r
\r
+int32_t Rm_createTreeAllocator(Rm_Inst *rmInst, const char *resourceName, Rm_ResourceRange *range)\r
+{\r
+ Rm_Allocator *allocator = NULL;\r
+ Rm_ResourceTree *treeRootEntry = NULL;\r
+ Rm_ResourceTreeNode *treeNode = NULL;\r
+ Rm_ResourceTreeNode *collidingNode = NULL;\r
+\r
+ /* Create the new base integer allocator */\r
+ allocator = Rm_allocatorAdd(rmInst, resourceName, Rm_allocatorType_TREE);\r
+\r
+ /* Create the tree root entry and initialize it */\r
+ treeRootEntry = Rm_osalMalloc(sizeof(Rm_ResourceTree));\r
+ RB_INIT(treeRootEntry);\r
+\r
+ /* Create a node in the tree for resource range and insert them into the tree. */\r
+ while (range != NULL)\r
+ {\r
+ treeNode = Rm_osalMalloc(sizeof(Rm_ResourceTreeNode));\r
+ treeNode->base = range->base;\r
+ treeNode->length = range->length;\r
+ /* Initialize the allocatedTo field to the NOT_ALLOCATED string */\r
+ strcpy(treeNode->allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+\r
+ /* Insert the node into the tree */\r
+ collidingNode = RB_INSERT(_Rm_ResourceTree, treeRootEntry, treeNode);\r
+\r
+ if (collidingNode)\r
+ {\r
+ Rm_ResourceTreeNode *nextNode = NULL;\r
+ \r
+ /* Node that was inserted colliding with an existing node. Clean up the tree\r
+ * that's been allocated thus far and return an error since there should be no\r
+ * collisions */\r
+ for (treeNode = RB_MIN(_Rm_ResourceTree, treeRootEntry); treeNode != NULL; treeNode = nextNode)\r
+ {\r
+ nextNode = RB_NEXT(_Rm_ResourceTree, treeRootEntry, treeNode);\r
+ RB_REMOVE(_Rm_ResourceTree, treeRootEntry, nextNode);\r
+ Rm_osalFree((void *)treeNode, sizeof(Rm_ResourceTreeNode));\r
+ }\r
+ /* Delete the tree root entry and the allocator */\r
+ Rm_osalFree((void *)treeRootEntry, sizeof(Rm_ResourceTree));\r
+ Rm_allocatorDelete(rmInst, allocator->resourceName);\r
+ return (-24); /* TODO FIX RETURN */\r
+ }\r
+\r
+ range = range->nextRange;\r
+ }\r
+\r
+ /* Assign the tree's root to the allocator */\r
+ allocator->allocatorRootEntry = treeRootEntry;\r
+\r
+ /* Print the base values as a test */\r
+ RB_FOREACH(treeNode, _Rm_ResourceTree, (Rm_ResourceTree *) allocator->allocatorRootEntry)\r
+ {\r
+ Rm_osalLog("Tree node base: %d length: %d and allocated to: %s\n", treeNode->base, treeNode->length, treeNode->allocatedTo);\r
+ }\r
+\r
+ return(0); /* TODO: FIX THIS RETURN */\r
+}\r
+\r
int32_t Rm_createAndInitAllocator(Rm_Inst *rmInst, const char *resourceName, \r
Rm_ResourceProperties *resourceProperties)\r
{\r
else if (strcmp(allocatorType, &rmTreeAllocator[0]) == 0)\r
{\r
/* Create a tree allocator using the resource properties */\r
+ retVal = Rm_createTreeAllocator(rmInst, resourceName, range); \r
}\r
else\r
{\r
@@ -670,92 +811,313 @@ int32_t Rm_parseResourceNode(Rm_Inst *rmInst, void *globalResourceDtb, int32_t n
return (RM_DTB_UTIL_RESULT_OKAY);\r
}\r
\r
-int32_t Rm_initializeAllocators(Rm_Inst *rmInst, void *globalResourceDtb)\r
+/* Called when an allocate request is made but the base is unspecified. RM must preallocate\r
+ * resources which then must be checked against the RM policy for the instance. If the\r
+ * policy does not agree another resource(s) must be preallocated and tested against the \r
+ * policy. Policy will provide initialize the preallocate with the base that it allows\r
+ * for the rm instance for the specified resource. */\r
+int32_t Rm_integerPreAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
{\r
- int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;\r
- int32_t startDepth = RM_DTB_UTIL_STARTING_DEPTH;\r
- int32_t result = RM_DTB_UTIL_RESULT_OKAY;\r
-\r
- /* Recursively parse the Global Resource List, creating an allocator for\r
- * each resource as specified in the node */\r
- result = Rm_parseResourceNode(rmInst, globalResourceDtb, nodeOffset, startDepth);\r
-\r
- return(result);\r
+ \r
}\r
- \r
-int32_t Rm_reserveLinuxResources(void *linuxResourceDtb)\r
+\r
+int32_t Rm_integerAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
{\r
- return(0);\r
+ Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
+ uint16_t resourceIndex, i, j;\r
+ bool resourcesValidated = TRUE;\r
+ int32_t retVal;\r
+\r
+ /* Find the specified resource base within the allocator */\r
+ for (resourceIndex = 0; resourceIndex < root->numResourceElements; resourceIndex++)\r
+ {\r
+ if (root->resourceArrayBase[resourceIndex].value == opInfo->resourceInfo->base)\r
+ {\r
+ /* Found the resource base in the allocator. Break from the loop */\r
+ break;\r
+ }\r
+ }\r
+\r
+ /* Only execute the allocate operation if the resource base was found in the allocator\r
+ * and the base+range does not exceed the number of entries in the allocator */\r
+ if (resourceIndex + opInfo->resourceInfo->range <= root->numResourceElements)\r
+ {\r
+ /* Verify all resource values from base to base+range exist in the allocator and\r
+ * are not allocated to another instance. */\r
+ for (i = resourceIndex, j = opInfo->resourceInfo->base; \r
+ i < (resourceIndex + opInfo->resourceInfo->range);\r
+ i++, j++)\r
+ {\r
+ if (root->resourceArrayBase[i].value != j)\r
+ {\r
+ /* A value in the range did not match. */\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+ resourcesValidated = FALSE;\r
+ break;\r
+ }\r
+ else if (strcmp(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING) != 0)\r
+ {\r
+ /* A value in the range is already allocated. */\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_ALLOCATED;\r
+ resourcesValidated = FALSE;\r
+ break; \r
+ }\r
+ }\r
\r
+ if (resourcesValidated)\r
+ {\r
+ /* Allocate all resources from base to base+range */\r
+ for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->range); i++)\r
+ {\r
+ strcpy(root->resourceArrayBase[i].allocatedTo, opInfo->srcInstName);\r
+ }\r
+ retVal = RM_SERVICE_APPROVED_AND_COMPLETED;\r
+ }\r
+ }\r
+ else\r
+ {\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+ }\r
+\r
+ return(retVal); \r
}\r
\r
-void Rm_allocationHandler (Rm_Inst *rmInst, Rm_Transaction *transaction)\r
+int32_t Rm_integerFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
{\r
- if (rmInst->instType == Rm_instType_CLIENT_DELEGATE)\r
+ Rm_IntegerAllocatorRootEntry *root = allocator->allocatorRootEntry;\r
+ uint16_t resourceIndex, i, j;\r
+ bool resourcesValidated = TRUE;\r
+ int32_t retVal;\r
+\r
+ /* Find the specified resource base within the allocator */\r
+ for (resourceIndex = 0; resourceIndex < root->numResourceElements; resourceIndex++)\r
{\r
-#if 0 \r
- /* Check local policy to see if the request can be satisfied with the\r
- * resources stored locally */\r
- Rm_policy...API()\r
+ if (root->resourceArrayBase[resourceIndex].value == opInfo->resourceInfo->base)\r
+ {\r
+ /* Found the resource base in the allocator. Break from the loop */\r
+ break;\r
+ }\r
+ }\r
\r
- if (policy check approves the resource)\r
+ /* Only execute the free operation if the resource base was found in the allocator\r
+ * and the base+range does not exceed the number of entries in the allocator */\r
+ if (resourceIndex + opInfo->resourceInfo->range <= root->numResourceElements)\r
+ {\r
+ /* Verify all resource values from base to base+range exist in the allocator,\r
+ * were not already free and were allocated to the instance that is the source\r
+ * of the free request. */\r
+ for (i = resourceIndex, j = opInfo->resourceInfo->base; \r
+ i < (resourceIndex + opInfo->resourceInfo->range);\r
+ i++, j++)\r
{\r
- /* call the allocator to allocate the resource */\r
- if (allocator returns resource)\r
+ if (root->resourceArrayBase[i].value != j)\r
{\r
- /* Populate the transaction with the allocated resources and the result */\r
- transaction->state = approve reason;\r
- return ...\r
+ /* A value in the range did not match. */\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+ resourcesValidated = FALSE;\r
+ break;\r
}\r
- else\r
+ else if (strcmp(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING) == 0)\r
{\r
- /* allocator ran out of resources, need to contact Server for more\r
- * resources */\r
- Rm_resourcePoolModRequest(...);\r
+ /* A value in the range is already free. */\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_ALREADY_FREE;\r
+ resourcesValidated = FALSE;\r
+ break; \r
+ } \r
+ else if (strcmp(root->resourceArrayBase[i].allocatedTo, opInfo->srcInstName) != 0)\r
+ {\r
+ /* A value in the range was not allocated to the source of\r
+ * the free request */\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_NOT_ALLOCATED_TO_INSTANCE_REQUESTING_THE_SERVICE;\r
+ resourcesValidated = FALSE;\r
+ break;\r
}\r
}\r
- else if (policy check denies resource)\r
+\r
+ if (resourcesValidated)\r
{\r
- /* Policy check denied resource. */\r
- transaction->state= deny reason;\r
- return ...\r
+ /* Free all resources from base to base+range */\r
+ for (i = resourceIndex; i < (resourceIndex + opInfo->resourceInfo->range); i++)\r
+ {\r
+ strcpy(root->resourceArrayBase[i].allocatedTo, RM_NOT_ALLOCATED_STRING);\r
+ }\r
+ retVal = RM_SERVICE_APPROVED_AND_COMPLETED;\r
}\r
- else if (policy check says forward to Server for validation)\r
+ }\r
+ else\r
+ {\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_VALUE_IN_RANGE_DOES_NOT_EXIST;\r
+ }\r
+\r
+ return(retVal);\r
+}\r
+\r
+/* Called when an allocate request is made but the base is unspecified. RM must preallocate\r
+ * resources which then must be checked against the RM policy for the instance. If the\r
+ * policy does not agree another resource(s) must be preallocated and tested against the \r
+ * policy */\r
+int32_t Rm_treePreAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+\r
+}\r
+\r
+int32_t Rm_treeAllocate(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+ \r
+}\r
+\r
+int32_t Rm_treeFree(Rm_Allocator *allocator, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+\r
+}\r
+\r
+int32_t Rm_allocatorOperation(Rm_Inst *rmInst, Rm_AllocatorOpInfo *opInfo)\r
+{\r
+ Rm_Allocator *allocator = NULL;\r
+ int32_t retVal;\r
+ void *key;\r
+\r
+ /* Lock access to the RM instance's transaction queue */\r
+ key = Rm_osalMtCsEnter();\r
+\r
+ /* Get the specified resource's allocator */\r
+ allocator = Rm_allocatorFind(rmInst, opInfo->resourceInfo->name);\r
+\r
+ if (allocator)\r
+ {\r
+ /* Call the allocator's type-based allocation function */\r
+ if(allocator->type == Rm_allocatorType_INTEGER)\r
{\r
- /* Forward the transaction to the Server */\r
- Rm_transactionForwarder(rmInst, transaction);\r
+ if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE)\r
+ {\r
+ retVal = Rm_integerPreAllocateUnspecified(allocator, opInfo);\r
+ } \r
+ else if (opInfo->operation == Rm_allocatorOp_ALLOCATE)\r
+ {\r
+ retVal = Rm_integerAllocate(allocator, opInfo);\r
+ }\r
+ else if (opInfo->operation == Rm_allocatorOp_FREE)\r
+ {\r
+ retVal = Rm_integerFree(allocator, opInfo);\r
+ }\r
}\r
-#endif \r
+ else if (allocator->type == Rm_allocatorType_TREE)\r
+ {\r
+ if (opInfo->operation == Rm_allocatorOp_PRE_ALLOCATE)\r
+ {\r
+ retVal = Rm_treePreAllocateUnspecified(allocator, opInfo);\r
+ } \r
+ else if (opInfo->operation == Rm_allocatorOp_ALLOCATE)\r
+ {\r
+ retVal = Rm_treeAllocate(allocator, opInfo);\r
+ }\r
+ else if (opInfo->operation == Rm_allocatorOp_FREE)\r
+ {\r
+ retVal = Rm_treeFree(allocator, opInfo);\r
+ } \r
+ } \r
}\r
- else if (rmInst->instType == Rm_instType_SERVER)\r
+ else\r
{\r
-#if 0 \r
- /* Check global policy to see if resource can be allocated. return result\r
- * no matter what */\r
- Rm_policy...API()\r
+ /* Allocator could not be found for resource */\r
+ retVal = RM_SERVICE_DENIED_RESOURCE_DOES_NOT_EXIST;\r
+ }\r
\r
- if (policy approves)\r
+ Rm_osalMtCsExit(key);\r
+ return(retVal);\r
+}\r
+\r
+void Rm_allocationHandler (Rm_Inst *rmInst, Rm_Transaction *transaction)\r
+{\r
+ if (rmInst->instType == Rm_instType_CLIENT_DELEGATE)\r
+ {\r
+#if 0 \r
+ if (resourceBase is unspecified)\r
{\r
- /* call allocator to allocate resource */\r
+ while (policy does not approve)\r
+ {\r
+ Rm_policy check get allowed base as starting point for prealloc\r
+ preallocate resource based on the range and alignment\r
+ Rm_policy...check\r
+ }\r
}\r
+ else\r
+ {\r
+ /* Check local policy to see if the request can be satisfied with the\r
+ * resources stored locally */\r
+ Rm_policy...API()\r
\r
- transaction->state = approve or deny reason;\r
- transaction->resourceInfo.base = ...;\r
- transaction->resourceInfo.range = ...;\r
-\r
- /* If source instance name does not match the current instance\r
- * name the allocation request came from a Client. The result\r
- * must be sent back to the Client */\r
- if (strcmp(transaction->sourceInstName, rmInst->name))\r
+ if (policy check approves the resource)\r
+ {\r
+ /* call the allocator to allocate the resource */\r
+ if (allocator returns resource)\r
+ {\r
+ /* Populate the transaction with the allocated resources and the result */\r
+ transaction->state = approve reason;\r
+ return ...\r
+ }\r
+ else\r
+ {\r
+ /* allocator ran out of resources, need to contact Server for more\r
+ * resources */\r
+ Rm_resourcePoolModRequest(...);\r
+ }\r
+ }\r
+ else if (policy check denies resource)\r
+ {\r
+ /* Policy check denied resource. */\r
+ transaction->state= deny reason;\r
+ return ...\r
+ }\r
+ else if (policy check says forward to Server for validation)\r
+ {\r
+ /* Forward the transaction to the Server */\r
+ Rm_transactionForwarder(rmInst, transaction);\r
+ }\r
+ }\r
+#endif \r
+ }\r
+ else if (rmInst->instType == Rm_instType_SERVER)\r
+ {\r
+#if 0 \r
+ if (resourceBase is unspecified)\r
{\r
- /* Names don't match. Send the transaction back to the Client */\r
- Rm_transactionResponder(rmInst, transaction);\r
+ while (policy does not approve)\r
+ {\r
+ Rm_policy check get allowed base as starting point for prealloc\r
+ preallocate resource based on the range and alignment\r
+ Rm_policy...check\r
+ }\r
}\r
else\r
{\r
- /* Resource allocation request originated locally on the active\r
- * instance. Send the response via the service responder. */ \r
- Rm_serviceResponder(rmInst, transaction); \r
+ /* Check global policy to see if resource can be allocated. return result\r
+ * no matter what */\r
+ Rm_policy...API()\r
+\r
+ if (policy approves)\r
+ {\r
+ /* call allocator to allocate resource */\r
+ }\r
+\r
+ transaction->state = approve or deny reason;\r
+ transaction->resourceInfo.base = ...;\r
+ transaction->resourceInfo.range = ...;\r
+\r
+ /* If source instance name does not match the current instance\r
+ * name the allocation request came from a Client. The result\r
+ * must be sent back to the Client */\r
+ if (strcmp(transaction->sourceInstName, rmInst->name))\r
+ {\r
+ /* Names don't match. Send the transaction back to the Client */\r
+ Rm_transactionResponder(rmInst, transaction);\r
+ }\r
+ else\r
+ {\r
+ /* Resource allocation request originated locally on the active\r
+ * instance. Send the response via the service responder. */ \r
+ Rm_serviceResponder(rmInst, transaction); \r
+ }\r
}\r
#endif \r
} \r
if (Rm_nsAddObject(rmInst, transaction->resourceInfo.nsName,\r
transaction->resourceInfo.base) == RM_NS_ACTION_APPROVED)\r
{\r
- transaction->state = RM_SERVICE_APPROVED;\r
+ transaction->state = RM_SERVICE_APPROVED_AND_COMPLETED;\r
}\r
else\r
{\r
if (Rm_nsDeleteObject(rmInst, transaction->resourceInfo.nsName) == \r
RM_NS_ACTION_APPROVED)\r
{\r
- transaction->state = RM_SERVICE_APPROVED;\r
+ transaction->state = RM_SERVICE_APPROVED_AND_COMPLETED;\r
}\r
else\r
{\r
}\r
}\r
\r
+int32_t Rm_initializeAllocators(Rm_Inst *rmInst, void *globalResourceDtb)\r
+{\r
+ int32_t nodeOffset = RM_DTB_UTIL_STARTING_NODE_OFFSET;\r
+ int32_t startDepth = RM_DTB_UTIL_STARTING_DEPTH;\r
+ int32_t result = RM_DTB_UTIL_RESULT_OKAY;\r
+\r
+ /* Recursively parse the Global Resource List, creating an allocator for\r
+ * each resource as specified in the node */\r
+ result = Rm_parseResourceNode(rmInst, globalResourceDtb, nodeOffset, startDepth);\r
+\r
+ return(result);\r
+}\r
+ \r
+int32_t Rm_reserveLinuxResources(Rm_Inst *rmInst, void *linuxResourceDtb)\r
+{\r
+ return(0);\r
+\r
+}\r
+\r
/**********************************************************************\r
********************** Application visible APIs **********************\r
**********************************************************************/\r
{\r
linuxResourceDtb = initCfg->linuxDtb;\r
fdt_open_into(linuxResourceDtb, linuxResourceDtb, fdt_totalsize(linuxResourceDtb)); \r
- Rm_reserveLinuxResources(linuxResourceDtb);\r
+ Rm_reserveLinuxResources(rmInst, linuxResourceDtb);\r
}\r
}\r
\r
diff --git a/src/rm_nameserver.c b/src/rm_nameserver.c
index 9abbe2b325a95c745c762b0ba459b884c3093f4c..858a9931974ad65684eca59072ff6eb779f68027 100644 (file)
--- a/src/rm_nameserver.c
+++ b/src/rm_nameserver.c
/**
- * @file rmnameserver.c
+ * @file rm_nameserver.c
*
* @brief
* This is the Resource Manager NameServer source.
diff --git a/src/rm_policy.c b/src/rm_policy.c
index f2b11a58d10cfee01059a50a2095b535baf52e74..07525a7a148e2baaa38005b7d071e88400f533e6 100644 (file)
--- a/src/rm_policy.c
+++ b/src/rm_policy.c
/* RM internal API includes */
//#include <ti/drv/rm/include/rm_policyloc.h>
+#include <ti/drv/rm/include/rm_dtb_utilloc.h>
+
+/* RM LIBFDT includes */
+#include <ti/drv/rm/src/libfdt/libfdt.h>
/* RM OSAL layer */
#include <rm_osal.h>
diff --git a/src/rm_services.c b/src/rm_services.c
index 46d07fffea9ece00937f4c5ac7047e171a1fa917..fbe8119cd12ffa87294f2cf7f7fd087d99615bf2 100644 (file)
--- a/src/rm_services.c
+++ b/src/rm_services.c
* via the provided callback function */
serviceResponse->serviceId = transaction->localId;
}
- else if (serviceResponse->serviceState == RM_SERVICE_APPROVED)
+ else if (serviceResponse->serviceState == RM_SERVICE_APPROVED_AND_COMPLETED)
{
/* Service was approved and service was an allocate request the resource
* data is passed back to the component */
/* Service was approved and service was an allocate request. The resource
* data is passed back to the component */
- if ((serviceResponse.serviceState == RM_SERVICE_APPROVED) &&
+ if ((serviceResponse.serviceState == RM_SERVICE_APPROVED_AND_COMPLETED) &&
((transaction->type == Rm_service_RESOURCE_ALLOCATE) ||
(transaction->type == Rm_service_RESOURCE_BLOCK_ALLOCATE) ||
(transaction->type == Rm_service_RESOURCE_ALLOCATE_BY_NAME)))
diff --git a/src/rm_transport.c b/src/rm_transport.c
index 9864eae679a78ed33991a4d10a8b8b8488d05976..8c49337b3cdd74575cbe1d3a80045faa4a59bda8 100644 (file)
--- a/src/rm_transport.c
+++ b/src/rm_transport.c
/* Transfer the result of the request to the transaction */\r
transaction->state = resourceRespPkt->requestState;\r
\r
- if ((transaction->state == RM_SERVICE_APPROVED) &&\r
+ if ((transaction->state == RM_SERVICE_APPROVED_AND_COMPLETED) &&\r
((transaction->type == Rm_service_RESOURCE_ALLOCATE) ||\r
(transaction->type == Rm_service_RESOURCE_BLOCK_ALLOCATE) ||\r
(transaction->type == Rm_service_RESOURCE_ALLOCATE_BY_NAME)))\r