ref: ce0087be0d06ad6efc332ba0c8146aa29d439b2d
parent: f8c7281bf53970f2250bc03cb9dada3b80302614
author: ngkaho1234 <[email protected]>
date: Sun Oct 4 14:49:04 EDT 2015
EA supports code rewritten with the view of providing EA modification supports.
--- a/lwext4/ext4.c
+++ b/lwext4/ext4.c
@@ -736,23 +736,10 @@
{int private_ret;
struct ext4_xattr_ref xattr_ref;
- struct ext4_xattr_entry *found_entry = NULL;
- void *out_data = NULL;
- size_t out_len = 0;
private_ret = ext4_fs_get_xattr_ref(&f->mp->fs, &ref,
&xattr_ref);
if (private_ret == EOK) {ext4_dmask_set(EXT4_DEBUG_ALL);
- private_ret = ext4_xattr_lookup(&xattr_ref,
- EXT4_XATTR_INDEX_POSIX_ACL_ACCESS,
- "",
- 0,
- &found_entry,
- &out_data,
- &out_len);
- if (private_ret == EOK) {- private_ret;
- }
ext4_fs_put_xattr_ref(&xattr_ref);
}
}
--- /dev/null
+++ b/lwext4/ext4_rbtree.c
@@ -1,0 +1,462 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <[email protected]>
+ (C) 2002 David Woodhouse <[email protected]>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/lib/rbtree.c
+*/
+#include "ext4_rbtree.h"
+
+static void __ext4_rb_rotate_left(struct ext4_rb_node *node, struct ext4_rb_root *root)
+{+ struct ext4_rb_node *right = node->ext4_rb_right;
+ struct ext4_rb_node *parent = ext4_rb_parent(node);
+
+ if ((node->ext4_rb_right = right->ext4_rb_left))
+ ext4_rb_set_parent(right->ext4_rb_left, node);
+ right->ext4_rb_left = node;
+
+ ext4_rb_set_parent(right, parent);
+
+ if (parent) {+ if (node == parent->ext4_rb_left)
+ parent->ext4_rb_left = right;
+ else
+ parent->ext4_rb_right = right;
+ } else
+ root->ext4_rb_node = right;
+ ext4_rb_set_parent(node, right);
+}
+
+static void __ext4_rb_rotate_right(struct ext4_rb_node *node, struct ext4_rb_root *root)
+{+ struct ext4_rb_node *left = node->ext4_rb_left;
+ struct ext4_rb_node *parent = ext4_rb_parent(node);
+
+ if ((node->ext4_rb_left = left->ext4_rb_right))
+ ext4_rb_set_parent(left->ext4_rb_right, node);
+ left->ext4_rb_right = node;
+
+ ext4_rb_set_parent(left, parent);
+
+ if (parent) {+ if (node == parent->ext4_rb_right)
+ parent->ext4_rb_right = left;
+ else
+ parent->ext4_rb_left = left;
+ } else
+ root->ext4_rb_node = left;
+ ext4_rb_set_parent(node, left);
+}
+
+void ext4_rb_insert_color(struct ext4_rb_node *node, struct ext4_rb_root *root)
+{+ struct ext4_rb_node *parent, *gparent;
+
+ while ((parent = ext4_rb_parent(node)) && ext4_rb_is_red(parent)) {+ gparent = ext4_rb_parent(parent);
+
+ if (parent == gparent->ext4_rb_left) {+ {+ register struct ext4_rb_node *uncle =
+ gparent->ext4_rb_right;
+ if (uncle && ext4_rb_is_red(uncle)) {+ ext4_rb_set_black(uncle);
+ ext4_rb_set_black(parent);
+ ext4_rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->ext4_rb_right == node) {+ register struct ext4_rb_node *tmp;
+ __ext4_rb_rotate_left(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ ext4_rb_set_black(parent);
+ ext4_rb_set_red(gparent);
+ __ext4_rb_rotate_right(gparent, root);
+ } else {+ {+ register struct ext4_rb_node *uncle =
+ gparent->ext4_rb_left;
+ if (uncle && ext4_rb_is_red(uncle)) {+ ext4_rb_set_black(uncle);
+ ext4_rb_set_black(parent);
+ ext4_rb_set_red(gparent);
+ node = gparent;
+ continue;
+ }
+ }
+
+ if (parent->ext4_rb_left == node) {+ register struct ext4_rb_node *tmp;
+ __ext4_rb_rotate_right(parent, root);
+ tmp = parent;
+ parent = node;
+ node = tmp;
+ }
+
+ ext4_rb_set_black(parent);
+ ext4_rb_set_red(gparent);
+ __ext4_rb_rotate_left(gparent, root);
+ }
+ }
+
+ ext4_rb_set_black(root->ext4_rb_node);
+}
+
+static void __ext4_rb_erase_color(struct ext4_rb_node *node, struct ext4_rb_node *parent,
+ struct ext4_rb_root *root)
+{+ struct ext4_rb_node *other;
+
+ while ((!node || ext4_rb_is_black(node)) && node != root->ext4_rb_node) {+ if (parent->ext4_rb_left == node) {+ other = parent->ext4_rb_right;
+ if (ext4_rb_is_red(other)) {+ ext4_rb_set_black(other);
+ ext4_rb_set_red(parent);
+ __ext4_rb_rotate_left(parent, root);
+ other = parent->ext4_rb_right;
+ }
+ if ((!other->ext4_rb_left ||
+ ext4_rb_is_black(other->ext4_rb_left)) &&
+ (!other->ext4_rb_right ||
+ ext4_rb_is_black(other->ext4_rb_right))) {+ ext4_rb_set_red(other);
+ node = parent;
+ parent = ext4_rb_parent(node);
+ } else {+ if (!other->ext4_rb_right ||
+ ext4_rb_is_black(other->ext4_rb_right)) {+ ext4_rb_set_black(other->ext4_rb_left);
+ ext4_rb_set_red(other);
+ __ext4_rb_rotate_right(other, root);
+ other = parent->ext4_rb_right;
+ }
+ ext4_rb_set_color(other, ext4_rb_color(parent));
+ ext4_rb_set_black(parent);
+ ext4_rb_set_black(other->ext4_rb_right);
+ __ext4_rb_rotate_left(parent, root);
+ node = root->ext4_rb_node;
+ break;
+ }
+ } else {+ other = parent->ext4_rb_left;
+ if (ext4_rb_is_red(other)) {+ ext4_rb_set_black(other);
+ ext4_rb_set_red(parent);
+ __ext4_rb_rotate_right(parent, root);
+ other = parent->ext4_rb_left;
+ }
+ if ((!other->ext4_rb_left ||
+ ext4_rb_is_black(other->ext4_rb_left)) &&
+ (!other->ext4_rb_right ||
+ ext4_rb_is_black(other->ext4_rb_right))) {+ ext4_rb_set_red(other);
+ node = parent;
+ parent = ext4_rb_parent(node);
+ } else {+ if (!other->ext4_rb_left ||
+ ext4_rb_is_black(other->ext4_rb_left)) {+ ext4_rb_set_black(other->ext4_rb_right);
+ ext4_rb_set_red(other);
+ __ext4_rb_rotate_left(other, root);
+ other = parent->ext4_rb_left;
+ }
+ ext4_rb_set_color(other, ext4_rb_color(parent));
+ ext4_rb_set_black(parent);
+ ext4_rb_set_black(other->ext4_rb_left);
+ __ext4_rb_rotate_right(parent, root);
+ node = root->ext4_rb_node;
+ break;
+ }
+ }
+ }
+ if (node)
+ ext4_rb_set_black(node);
+}
+
+void __ext4_rb_erase(struct ext4_rb_node *node, struct ext4_rb_root *root)
+{+ struct ext4_rb_node *child, *parent;
+ int color;
+
+ if (!node->ext4_rb_left)
+ child = node->ext4_rb_right;
+ else if (!node->ext4_rb_right)
+ child = node->ext4_rb_left;
+ else {+ struct ext4_rb_node *old = node, *left;
+
+ node = node->ext4_rb_right;
+ while ((left = node->ext4_rb_left) != NULL)
+ node = left;
+
+ if (ext4_rb_parent(old)) {+ if (ext4_rb_parent(old)->ext4_rb_left == old)
+ ext4_rb_parent(old)->ext4_rb_left = node;
+ else
+ ext4_rb_parent(old)->ext4_rb_right = node;
+ } else
+ root->ext4_rb_node = node;
+
+ child = node->ext4_rb_right;
+ parent = ext4_rb_parent(node);
+ color = ext4_rb_color(node);
+
+ if (parent == old) {+ parent = node;
+ } else {+ if (child)
+ ext4_rb_set_parent(child, parent);
+ parent->ext4_rb_left = child;
+
+ node->ext4_rb_right = old->ext4_rb_right;
+ ext4_rb_set_parent(old->ext4_rb_right, node);
+ }
+
+ node->ext4_rb_parent_color = old->ext4_rb_parent_color;
+ node->ext4_rb_left = old->ext4_rb_left;
+ ext4_rb_set_parent(old->ext4_rb_left, node);
+
+ goto color;
+ }
+
+ parent = ext4_rb_parent(node);
+ color = ext4_rb_color(node);
+
+ if (child)
+ ext4_rb_set_parent(child, parent);
+ if (parent) {+ if (parent->ext4_rb_left == node)
+ parent->ext4_rb_left = child;
+ else
+ parent->ext4_rb_right = child;
+ } else
+ root->ext4_rb_node = child;
+
+color:
+ if (color == EXT4_RB_BLACK)
+ __ext4_rb_erase_color(child, parent, root);
+}
+
+static void ext4_rb_augment_path(struct ext4_rb_node *node, ext4_rb_augment_f func,
+ void *data)
+{+ struct ext4_rb_node *parent;
+
+up:
+ func(node, data);
+ parent = ext4_rb_parent(node);
+ if (!parent)
+ return;
+
+ if (node == parent->ext4_rb_left && parent->ext4_rb_right)
+ func(parent->ext4_rb_right, data);
+ else if (parent->ext4_rb_left)
+ func(parent->ext4_rb_left, data);
+
+ node = parent;
+ goto up;
+}
+
+/*
+ * after inserting @node into the tree, update the tree to account for
+ * both the new entry and any damage done by rebalance
+ */
+void ext4_rb_augment_insert(struct ext4_rb_node *node, ext4_rb_augment_f func,
+ void *data)
+{+ if (node->ext4_rb_left)
+ node = node->ext4_rb_left;
+ else if (node->ext4_rb_right)
+ node = node->ext4_rb_right;
+
+ ext4_rb_augment_path(node, func, data);
+}
+
+/*
+ * before removing the node, find the deepest node on the rebalance path
+ * that will still be there after @node gets removed
+ */
+struct ext4_rb_node *ext4_rb_augment_erase_begin(struct ext4_rb_node *node)
+{+ struct ext4_rb_node *deepest;
+
+ if (!node->ext4_rb_right && !node->ext4_rb_left)
+ deepest = ext4_rb_parent(node);
+ else if (!node->ext4_rb_right)
+ deepest = node->ext4_rb_left;
+ else if (!node->ext4_rb_left)
+ deepest = node->ext4_rb_right;
+ else {+ deepest = ext4_rb_next(node);
+ if (deepest->ext4_rb_right)
+ deepest = deepest->ext4_rb_right;
+ else if (ext4_rb_parent(deepest) != node)
+ deepest = ext4_rb_parent(deepest);
+ }
+
+ return deepest;
+}
+
+/*
+ * after removal, update the tree to account for the removed entry
+ * and any rebalance damage.
+ */
+void ext4_rb_augment_erase_end(struct ext4_rb_node *node, ext4_rb_augment_f func,
+ void *data)
+{+ if (node)
+ ext4_rb_augment_path(node, func, data);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct ext4_rb_node *ext4_rb_first(const struct ext4_rb_root *root)
+{+ struct ext4_rb_node *n;
+
+ n = root->ext4_rb_node;
+ if (!n)
+ return NULL;
+ while (n->ext4_rb_left)
+ n = n->ext4_rb_left;
+ return n;
+}
+
+struct ext4_rb_node *ext4_rb_last(const struct ext4_rb_root *root)
+{+ struct ext4_rb_node *n;
+
+ n = root->ext4_rb_node;
+ if (!n)
+ return NULL;
+ while (n->ext4_rb_right)
+ n = n->ext4_rb_right;
+ return n;
+}
+
+struct ext4_rb_node *ext4_rb_next(const struct ext4_rb_node *node)
+{+ struct ext4_rb_node *parent;
+
+ if (ext4_rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a right-hand child, go down and then left as far
+ as we can. */
+ if (node->ext4_rb_right) {+ node = node->ext4_rb_right;
+ while (node->ext4_rb_left)
+ node = node->ext4_rb_left;
+ return (struct ext4_rb_node *)node;
+ }
+
+ /* No right-hand children. Everything down and left is
+ smaller than us, so any 'next' node must be in the general
+ direction of our parent. Go up the tree; any time the
+ ancestor is a right-hand child of its parent, keep going
+ up. First time it's a left-hand child of its parent, said
+ parent is our 'next' node. */
+ while ((parent = ext4_rb_parent(node)) && node == parent->ext4_rb_right)
+ node = parent;
+
+ return parent;
+}
+
+struct ext4_rb_node *ext4_rb_prev(const struct ext4_rb_node *node)
+{+ struct ext4_rb_node *parent;
+
+ if (ext4_rb_parent(node) == node)
+ return NULL;
+
+ /* If we have a left-hand child, go down and then right as far
+ as we can. */
+ if (node->ext4_rb_left) {+ node = node->ext4_rb_left;
+ while (node->ext4_rb_right)
+ node = node->ext4_rb_right;
+ return (struct ext4_rb_node *)node;
+ }
+
+ /* No left-hand children. Go up till we find an ancestor which
+ is a right-hand child of its parent */
+ while ((parent = ext4_rb_parent(node)) && node == parent->ext4_rb_left)
+ node = parent;
+
+ return parent;
+}
+
+void ext4_rb_replace_node(struct ext4_rb_node *victim, struct ext4_rb_node *new,
+ struct ext4_rb_root *root)
+{+ struct ext4_rb_node *parent = ext4_rb_parent(victim);
+
+ /* Set the surrounding nodes to point to the replacement */
+ if (parent) {+ if (victim == parent->ext4_rb_left)
+ parent->ext4_rb_left = new;
+ else
+ parent->ext4_rb_right = new;
+ } else {+ root->ext4_rb_node = new;
+ }
+ if (victim->ext4_rb_left)
+ ext4_rb_set_parent(victim->ext4_rb_left, new);
+ if (victim->ext4_rb_right)
+ ext4_rb_set_parent(victim->ext4_rb_right, new);
+
+ /* Copy the pointers/colour from the victim to the replacement */
+ *new = *victim;
+}
+
+void ext4_rb_erase(struct ext4_rb_node *node, struct ext4_rb_root *root)
+{+ __ext4_rb_erase(node, root);
+}
+
+void ext4_rb_insert(struct ext4_rb_root *root, struct ext4_rb_node *node,
+ int (*cmp)(struct ext4_rb_node *, struct ext4_rb_node *))
+{+ struct ext4_rb_node **new = &(root->ext4_rb_node), *parent = NULL;
+
+ /* Figure out where to put new node */
+ while (*new) {+ int result = cmp(node, *new);
+
+ parent = *new;
+ if (result < 0) {+ new = &((*new)->ext4_rb_left);
+ } else if (result > 0) {+ new = &((*new)->ext4_rb_right);
+ } else
+ return;
+ }
+
+ /* Add new node and rebalance tree. */
+ ext4_rb_link_node(node, parent, new);
+ ext4_rb_insert_color(node, root);
+}
--- /dev/null
+++ b/lwext4/ext4_rbtree.h
@@ -1,0 +1,201 @@
+/*
+ Red Black Trees
+ (C) 1999 Andrea Arcangeli <[email protected]>
+
+ This program is free software; you can redistribute it and/or modify
+ it under the terms of the GNU General Public License as published by
+ the Free Software Foundation; either version 2 of the License, or
+ (at your option) any later version.
+
+ This program is distributed in the hope that it will be useful,
+ but WITHOUT ANY WARRANTY; without even the implied warranty of
+ MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ GNU General Public License for more details.
+
+ You should have received a copy of the GNU General Public License
+ along with this program; if not, write to the Free Software
+ Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+
+ linux/include/linux/rbtree.h
+
+ To use rbtrees you'll have to implement your own insert and search cores.
+ This will avoid us to use callbacks and to drop drammatically performances.
+ I know it's not the cleaner way, but in C (not in C++) to get
+ performances and genericity...
+
+ Some example of insert and search follows here. The search is a plain
+ normal search over an ordered tree. The insert instead must be implemented
+ in two steps: First, the code must insert the element in order as a red leaf
+ in the tree, and then the support library function ext4_rb_insert_color() must
+ be called. Such function will do the not trivial work to rebalance the
+ rbtree, if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * ext4_rb_search_page_cache(struct inode * inode,
+ unsigned long offset)
+{+ struct ext4_rb_node * n = inode->i_ext4_rb_page_cache.ext4_rb_node;
+ struct page * page;
+
+ while (n)
+ {+ page = ext4_rb_entry(n, struct page, ext4_rb_page_cache);
+
+ if (offset < page->offset)
+ n = n->ext4_rb_left;
+ else if (offset > page->offset)
+ n = n->ext4_rb_right;
+ else
+ return page;
+ }
+ return NULL;
+}
+
+static inline struct page * __ext4_rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct ext4_rb_node * node)
+{+ struct ext4_rb_node ** p = &inode->i_ext4_rb_page_cache.ext4_rb_node;
+ struct ext4_rb_node * parent = NULL;
+ struct page * page;
+
+ while (*p)
+ {+ parent = *p;
+ page = ext4_rb_entry(parent, struct page, ext4_rb_page_cache);
+
+ if (offset < page->offset)
+ p = &(*p)->ext4_rb_left;
+ else if (offset > page->offset)
+ p = &(*p)->ext4_rb_right;
+ else
+ return page;
+ }
+
+ ext4_rb_link_node(node, parent, p);
+
+ return NULL;
+}
+
+static inline struct page * ext4_rb_insert_page_cache(struct inode * inode,
+ unsigned long offset,
+ struct ext4_rb_node * node)
+{+ struct page * ret;
+ if ((ret = __ext4_rb_insert_page_cache(inode, offset, node)))
+ goto out;
+ ext4_rb_insert_color(node, &inode->i_ext4_rb_page_cache);
+ out:
+ return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef EXT4_RBTREE_H_
+#define EXT4_RBTREE_H_
+
+#include <stddef.h>
+#include <stdbool.h>
+
+#ifndef offsetof
+#define offsetof(type, member) ((size_t) & ((type *)0)->member)
+#endif
+#ifndef container_of
+#define container_of(ptr, type, member) \
+ ((type *)((char *)(ptr) - (unsigned long)(&((type *)0)->member)))
+#endif
+
+struct ext4_rb_node
+{+ unsigned long ext4_rb_parent_color;
+#define EXT4_RB_RED 0
+#define EXT4_RB_BLACK 1
+ struct ext4_rb_node *ext4_rb_right;
+ struct ext4_rb_node *ext4_rb_left;
+};
+/* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct ext4_rb_root
+{+ struct ext4_rb_node *ext4_rb_node;
+};
+
+#define ext4_rb_parent(r) ((struct ext4_rb_node *)((r)->ext4_rb_parent_color & ~3))
+#define ext4_rb_color(r) ((r)->ext4_rb_parent_color & 1)
+#define ext4_rb_is_red(r) (!ext4_rb_color(r))
+#define ext4_rb_is_black(r) ext4_rb_color(r)
+#define ext4_rb_set_red(r) \
+ do { \+ (r)->ext4_rb_parent_color &= ~1; \
+ } while (0)
+#define ext4_rb_set_black(r) \
+ do { \+ (r)->ext4_rb_parent_color |= 1; \
+ } while (0)
+
+static inline void ext4_rb_set_parent(struct ext4_rb_node *rb, struct ext4_rb_node *p)
+{+ rb->ext4_rb_parent_color =
+ (rb->ext4_rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void ext4_rb_set_color(struct ext4_rb_node *rb, int color)
+{+ rb->ext4_rb_parent_color = (rb->ext4_rb_parent_color & ~1) | color;
+}
+
+#define EXT4_RB_ROOT \
+ (struct ext4_rb_root) \
+ { \+ NULL, \
+ }
+#define ext4_rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define EXT4_RB_EMPTY_ROOT(root) ((root)->ext4_rb_node == NULL)
+#define EXT4_RB_EMPTY_NODE(node) (ext4_rb_parent(node) == node)
+#define EXT4_RB_CLEAR_NODE(node) (ext4_rb_set_parent(node, node))
+
+static inline void ext4_rb_init_node(struct ext4_rb_node *rb)
+{+ rb->ext4_rb_parent_color = 0;
+ rb->ext4_rb_right = NULL;
+ rb->ext4_rb_left = NULL;
+ EXT4_RB_CLEAR_NODE(rb);
+}
+
+extern void ext4_rb_insert_color(struct ext4_rb_node *, struct ext4_rb_root *);
+extern void ext4_rb_erase(struct ext4_rb_node *, struct ext4_rb_root *);
+
+typedef void (*ext4_rb_augment_f)(struct ext4_rb_node *node, void *data);
+
+extern void ext4_rb_augment_insert(struct ext4_rb_node *node, ext4_rb_augment_f func,
+ void *data);
+extern struct ext4_rb_node *ext4_rb_augment_erase_begin(struct ext4_rb_node *node);
+extern void ext4_rb_augment_erase_end(struct ext4_rb_node *node, ext4_rb_augment_f func,
+ void *data);
+
+/* Find logical next and previous nodes in a tree */
+extern struct ext4_rb_node *ext4_rb_next(const struct ext4_rb_node *);
+extern struct ext4_rb_node *ext4_rb_prev(const struct ext4_rb_node *);
+extern struct ext4_rb_node *ext4_rb_first(const struct ext4_rb_root *);
+extern struct ext4_rb_node *ext4_rb_last(const struct ext4_rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void ext4_rb_replace_node(struct ext4_rb_node *victim, struct ext4_rb_node *new,
+ struct ext4_rb_root *root);
+
+static inline void ext4_rb_link_node(struct ext4_rb_node *node,
+ struct ext4_rb_node *parent,
+ struct ext4_rb_node **ext4_rb_link)
+{+ node->ext4_rb_parent_color = (unsigned long)parent;
+ node->ext4_rb_left = node->ext4_rb_right = NULL;
+
+ *ext4_rb_link = node;
+}
+
+extern void ext4_rb_erase(struct ext4_rb_node *, struct ext4_rb_root *);
+
+extern void ext4_rb_insert(struct ext4_rb_root *, struct ext4_rb_node *,
+ int (*)(struct ext4_rb_node *, struct ext4_rb_node *));
+
+#endif /* EXT4_RBTREE_H_ */
--- a/lwext4/ext4_types.h
+++ b/lwext4/ext4_types.h
@@ -44,6 +44,7 @@
#include "ext4_config.h"
#include "ext4_blockdev.h"
+#include "ext4_rbtree.h"
#include <stdint.h>
@@ -670,10 +671,22 @@
uint32_t e_hash; /* hash value of name and value */
} __attribute__((packed));
+struct ext4_xattr_item {+ uint8_t name_index;
+ char *name;
+ size_t name_len;
+ void *data;
+ size_t data_size;
+
+ struct ext4_rb_node node;
+};
+
struct ext4_xattr_ref {bool block_loaded;
struct ext4_block block;
struct ext4_inode_ref *inode_ref;
+ struct ext4_rb_root root;
+ bool dirty;
struct ext4_fs *fs;
};
--- a/lwext4/ext4_xattr.c
+++ b/lwext4/ext4_xattr.c
@@ -7,13 +7,155 @@
#include "ext4_debug.h"
#include "ext4_block_group.h"
#include "ext4_balloc.h"
-#include "ext4_bitmap.h"
#include "ext4_inode.h"
-#include "ext4_ialloc.h"
#include "ext4_extent.h"
#include <string.h>
+#include <stdlib.h>
+static int ext4_xattr_item_cmp(struct ext4_rb_node *a_,
+ struct ext4_rb_node *b_)
+{+ struct ext4_xattr_item *a, *b;
+ int result;
+ a = container_of(a_, struct ext4_xattr_item, node);
+ b = container_of(b_, struct ext4_xattr_item, node);
+ result = a->name_index - b->name_index;
+ if (result)
+ return result;
+
+ result = a->name_len - b->name_len;
+ if (result)
+ return result;
+
+ return memcmp(a->name, b->name, a->name_len);
+}
+
+static struct ext4_xattr_item *
+ext4_xattr_item_lookup(struct ext4_rb_root *root,
+ uint8_t name_index,
+ char *name,
+ size_t name_len)
+{+ struct ext4_rb_node *new = root->ext4_rb_node;
+
+ /* Figure out where to put new node */
+ while (new) {+ struct ext4_xattr_item *item =
+ container_of(new, struct ext4_xattr_item, node);
+ int result = name_index - item->name_index;
+ if (!result) {+ result = name_len - item->name_len;
+ if (!result)
+ result = memcmp(name,
+ item->name, name_len);
+
+ }
+
+ if (result < 0)
+ new = new->ext4_rb_left;
+ else if (result > 0)
+ new = new->ext4_rb_right;
+ else
+ return item;
+
+ }
+
+ return NULL;
+}
+
+static void
+ext4_xattr_item_insert(struct ext4_rb_root *root,
+ struct ext4_xattr_item *item)
+{+ ext4_rb_insert(root, &item->node, ext4_xattr_item_cmp);
+}
+
+static void
+ext4_xattr_item_remove(struct ext4_rb_root *root,
+ struct ext4_xattr_item *item)
+{+ ext4_rb_erase(&item->node, root);
+}
+
+
+static struct ext4_xattr_item *
+ext4_xattr_item_alloc(uint8_t name_index,
+ char *name,
+ size_t name_len)
+{+ struct ext4_xattr_item *item;
+ item = malloc(sizeof(struct ext4_xattr_item) +
+ name_len);
+ if (!item)
+ return NULL;
+
+ item->name_index = name_index;
+ item->name = (char *)(item + 1);
+ item->name_len = name_len;
+ item->data = NULL;
+ item->data_size = 0;
+
+ memset(&item->node, 0, sizeof(item->node));
+ memcpy(item->name, name, name_len);
+
+ return item;
+}
+
+static int
+ext4_xattr_item_alloc_data(struct ext4_xattr_item *item,
+ void *orig_data,
+ size_t data_size)
+{+ void *data = NULL;
+ ext4_assert(!item->data);
+ data = malloc(data_size);
+ if (!data)
+ return ENOMEM;
+
+ if (orig_data)
+ memcpy(data, orig_data, data_size);
+
+ item->data = data;
+ item->data_size = data_size;
+ return EOK;
+}
+
+static void
+ext4_xattr_item_free_data(struct ext4_xattr_item *item)
+{+ ext4_assert(item->data);
+ free(item->data);
+ item->data = NULL;
+ item->data_size = 0;
+}
+
+static int
+ext4_xattr_item_resize_data(struct ext4_xattr_item *item,
+ size_t new_data_size)
+{+ if (new_data_size != item->data_size) {+ void *new_data;
+ new_data = realloc(item->data, new_data_size);
+ if (!new_data)
+ return ENOMEM;
+
+ item->data = new_data;
+ item->data_size = new_data_size;
+ }
+ return EOK;
+}
+
+static void
+ext4_xattr_item_free(struct ext4_xattr_item *item)
+{+ if (item->data)
+ ext4_xattr_item_free_data(item);
+
+ free(item);
+}
+
+
static void *ext4_xattr_entry_data(struct ext4_xattr_ref *xattr_ref,
struct ext4_xattr_entry *entry,
bool in_inode)
@@ -46,16 +188,10 @@
return ret;
}
-static int ext4_xattr_block_lookup(struct ext4_xattr_ref *xattr_ref,
- uint8_t name_index,
- char *name,
- size_t name_len,
- struct ext4_xattr_entry **found_entry,
- void **out_data,
- size_t *out_len)
+static int ext4_xattr_block_fetch(struct ext4_xattr_ref *xattr_ref)
{+ int ret = EOK;
size_t size_rem;
- bool entry_found = false;
void *data;
struct ext4_xattr_entry *entry = NULL;
@@ -66,49 +202,45 @@
for(;size_rem > 0 && !EXT4_XATTR_IS_LAST_ENTRY(entry);
entry = EXT4_XATTR_NEXT(entry),
size_rem -= EXT4_XATTR_LEN(entry->e_name_len)) {- int diff = -1;
- if (name_index == entry->e_name_index &&
- name_len == entry->e_name_len) {- char *e_name = (char *)(entry + 1);
- diff = memcmp(e_name,
- name,
- name_len);
+ struct ext4_xattr_item *item;
+ char *e_name = (char *)(entry + 1);
+
+ data = ext4_xattr_entry_data(xattr_ref, entry,
+ false);
+ if (!data) {+ ret = EIO;
+ goto Finish;
}
- if (!diff) {- entry_found = true;
- break;
+
+ item = ext4_xattr_item_alloc(entry->e_name_index,
+ e_name,
+ (size_t)entry->e_name_len);
+ if (!item) {+ ret = ENOMEM;
+ goto Finish;
}
- }
- if (!entry_found)
- return ENOENT;
+ if (ext4_xattr_item_alloc_data(item,
+ data,
+ to_le32(entry->e_value_size)
+ != EOK)) {+ ext4_xattr_item_free(item);
+ ret = ENOMEM;
+ goto Finish;
+ }
+ ext4_xattr_item_insert(&xattr_ref->root,
+ item);
- data = ext4_xattr_entry_data(xattr_ref, entry,
- false);
- if (!data)
- return EIO;
-
- if (found_entry)
- *found_entry = entry;
-
- if (out_data && out_len) {- *out_data = data;
- *out_len = to_le32(entry->e_value_size);
}
- return EOK;
+Finish:
+ return ret;
}
-static int ext4_xattr_inode_lookup(struct ext4_xattr_ref *xattr_ref,
- uint8_t name_index,
- char *name,
- size_t name_len,
- struct ext4_xattr_entry **found_entry,
- void **out_data,
- size_t *out_len)
+static int ext4_xattr_inode_fetch(struct ext4_xattr_ref *xattr_ref)
{void *data;
size_t size_rem;
- bool entry_found = false;
+ int ret = EOK;
struct ext4_xattr_ibody_header *header = NULL;
struct ext4_xattr_entry *entry = NULL;
uint16_t inode_size = ext4_get16(&xattr_ref->fs->sb,
@@ -123,73 +255,72 @@
for(;size_rem > 0 && !EXT4_XATTR_IS_LAST_ENTRY(entry);
entry = EXT4_XATTR_NEXT(entry),
size_rem -= EXT4_XATTR_LEN(entry->e_name_len)) {- int diff = -1;
- if (name_index == entry->e_name_index &&
- name_len == entry->e_name_len) {- char *e_name = (char *)(entry + 1);
- diff = memcmp(e_name,
- name,
- name_len);
+ struct ext4_xattr_item *item;
+ char *e_name = (char *)(entry + 1);
+
+ data = ext4_xattr_entry_data(xattr_ref, entry,
+ true);
+ if (!data) {+ ret = EIO;
+ goto Finish;
}
- if (!diff) {- entry_found = true;
- break;
+
+ item = ext4_xattr_item_alloc(entry->e_name_index,
+ e_name,
+ (size_t)entry->e_name_len);
+ if (!item) {+ ret = ENOMEM;
+ goto Finish;
}
- }
- if (!entry_found)
- return ENOENT;
+ if (ext4_xattr_item_alloc_data(item,
+ data,
+ to_le32(entry->e_value_size)
+ != EOK)) {+ ext4_xattr_item_free(item);
+ ret = ENOMEM;
+ goto Finish;
+ }
+ ext4_xattr_item_insert(&xattr_ref->root,
+ item);
- data = ext4_xattr_entry_data(xattr_ref, entry,
- true);
- if (!data)
- return EIO;
- if (found_entry)
- *found_entry = entry;
-
- if (out_data && out_len) {- *out_data = data;
- *out_len = to_le32(entry->e_value_size);
}
- return EOK;
+Finish:
+ return ret;
}
-int ext4_xattr_lookup(struct ext4_xattr_ref *xattr_ref,
- uint8_t name_index,
- char *name,
- size_t name_len,
- struct ext4_xattr_entry **found_entry,
- void **out_data,
- size_t *out_len)
+static int ext4_xattr_fetch(struct ext4_xattr_ref *xattr_ref)
{- int ret = ENOENT;
+ int ret = EOK;
uint16_t inode_size = ext4_get16(&xattr_ref->fs->sb,
inode_size);
if (inode_size > EXT4_GOOD_OLD_INODE_SIZE) {- ret = ext4_xattr_inode_lookup(xattr_ref,
- name_index,
- name,
- name_len,
- found_entry,
- out_data,
- out_len);
- if (ret != ENOENT)
+ ret = ext4_xattr_inode_fetch(xattr_ref);
+ if (ret != EOK)
return ret;
}
if (xattr_ref->block_loaded)
- ret = ext4_xattr_block_lookup(xattr_ref,
- name_index,
- name,
- name_len,
- found_entry,
- out_data,
- out_len);
+ ret = ext4_xattr_block_fetch(xattr_ref);
+
+ xattr_ref->dirty = false;
return ret;
}
+static void
+ext4_xattr_purge_items(struct ext4_xattr_ref *xattr_ref)
+{+ struct ext4_rb_node *node;
+ while ((node = ext4_rb_first(&xattr_ref->root))) {+ struct ext4_xattr_item *item = ext4_rb_entry(
+ node, struct ext4_xattr_item, node);
+ ext4_xattr_item_remove(&xattr_ref->root, item);
+ ext4_xattr_item_free(item);
+ }
+}
+
int ext4_fs_get_xattr_ref(struct ext4_fs *fs,
struct ext4_inode_ref *inode_ref,
struct ext4_xattr_ref *ref)
@@ -198,6 +329,7 @@
uint64_t xattr_block;
xattr_block = ext4_inode_get_file_acl(inode_ref->inode,
&fs->sb);
+ memset(&ref->root, 0, sizeof(ref->root));
if (xattr_block) {rc = ext4_block_get(fs->bdev,
&inode_ref->block, xattr_block);
@@ -210,6 +342,16 @@
ref->inode_ref = inode_ref;
ref->fs = fs;
+
+ rc = ext4_xattr_fetch(ref);
+ if (rc != EOK) {+ ext4_xattr_purge_items(ref);
+ if (xattr_block)
+ ext4_block_set(fs->bdev, &inode_ref->block);
+
+ ref->block_loaded = false;
+ return rc;
+ }
return EOK;
}
@@ -219,6 +361,7 @@
ext4_block_set(ref->fs->bdev, &ref->block);
ref->block_loaded = false;
}
+ ext4_xattr_purge_items(ref);
ref->inode_ref = NULL;
ref->fs = NULL;
}
--- a/lwext4/ext4_xattr.h
+++ b/lwext4/ext4_xattr.h
@@ -10,12 +10,4 @@
void ext4_fs_put_xattr_ref(struct ext4_xattr_ref *ref);
-int ext4_xattr_lookup(struct ext4_xattr_ref *xattr_ref,
- uint8_t name_index,
- char *name,
- size_t name_len,
- struct ext4_xattr_entry **found_entry,
- void **out_data,
- size_t *out_len);
-
#endif