Skip to contentSkip to conversation

reiser4: fix problem of non-deletable directories

PATCH In review Edward Shishkin 3 participants 4 messages Sep 26, 2014 – Oct 12, 2014

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 reiser4: fix problem of non-deletable directories

Problem:
parse_cut() calculates cut mode incorrectly when the range contains objects with non-unique keys, e.g. directory items.

Scenario of corruption.
A node contains only one cde-item with 44 (#0-#43) units, and the units #42,#43 have identical keys (because of hash collision). We shift units #0-#42 to left. In this case parse_cut() jumps to the branch "removed completely". As the result the whole item is removed, while only units #0-#42 are copied to the left neighbor. unlink() can not find directory entry which corresponds to unexpectedly killed unit #43. rmdir() doesn't decrement size of the directory in the error path. As the result, the directory becomes non-deletable.

Fixup:
For ranges with non-unique keys use a special version of parse_cut(), which doesn't calculate cut mode by keys.

---
 fs/reiser4/plugin/node/node40.c |  148 ++++++++++++++++++++++++++++++++--------
 1 file changed, 122 insertions(+), 26 deletions(-)
fs/reiser4/plugin/node/node40.c +122 -26
@@ -1017,36 +1017,32 @@ int shrink_item_node40(coord_t * coord,
 	return 0;
 }
 
-/* this is used by cut_node40 and kill_node40. It analyses input parameters and calculates cut mode. There are 2 types
-   of cut. First is when a unit is removed from the middle of an item.  In this case this function returns 1. All the
-   rest fits into second case: 0 or 1 of items getting tail cut, 0 or more items removed completely and 0 or 1 item
-   getting head cut. Function returns 0 in this case */
-static int
-parse_cut(struct cut40_info *cinfo, const struct cut_kill_params *params)
+/*
+ * Evaluate cut mode, if key range has been specified.
+ *
+ * This is for the case when units are not minimal objects
+ * addressed by keys.
+ *
+ * This doesn't work when range contains objects with
+ * non-unique keys (e.g. directory items).
+ */
+static int parse_cut_by_key_range(struct cut40_info *cinfo,
+				  const struct cut_kill_params *params)
 {
-	reiser4_key left_key, right_key;
 	reiser4_key min_from_key, max_to_key;
-	const reiser4_key *from_key, *to_key;
-
-	init_cinfo(cinfo);
-
-	/* calculate minimal key stored in first item of items to be cut (params->from) */
+	const reiser4_key *from_key = params->from_key;
+	const reiser4_key *to_key = params->to_key;
+	/*
+	 * calculate minimal key stored in first item
+	 * of items to be cut (params->from)
+	 */
 	item_key_by_coord(params->from, &min_from_key);
-	/* and max key stored in last item of items to be cut (params->to) */
+	/*
+	 * calculate maximal key stored in last item
+	 * of items to be cut (params->to)
+	 */
 	max_item_key_by_coord(params->to, &max_to_key);
 
-	/* if cut key range is not defined in input parameters - define it using cut coord range */
-	if (params->from_key == NULL) {
-		assert("vs-1513", params->to_key == NULL);
-		unit_key_by_coord(params->from, &left_key);
-		from_key = &left_key;
-		max_unit_key_by_coord(params->to, &right_key);
-		to_key = &right_key;
-	} else {
-		from_key = params->from_key;
-		to_key = params->to_key;
-	}
-
 	if (params->from->item_pos == params->to->item_pos) {
 		if (keylt(&min_from_key, from_key)
 		    && keylt(to_key, &max_to_key))
@@ -1069,7 +1065,7 @@ parse_cut(struct cut40_info *cinfo, cons
 	} else {
 		cinfo->first_removed = params->from->item_pos + 1;
 		cinfo->removed_count =
-		    params->to->item_pos - params->from->item_pos - 1;
+			params->to->item_pos - params->from->item_pos - 1;
 
 		if (keygt(from_key, &min_from_key)) {
 			/* first item is not cut completely */
@@ -1089,10 +1085,110 @@ parse_cut(struct cut40_info *cinfo, cons
 		if (cinfo->removed_count)
 			cinfo->mode |= CMODE_WHOLE;
 	}
+	return 0;
+}
+
+/*
+ * Evaluate cut mode, if the key range hasn't been specified.
+ * In this case the range can include objects with non-unique
+ * keys (e.g. directory entries).
+ *
+ * This doesn't work when units are not the minimal objects
+ * addressed by keys (e.g. bytes in file's body stored in
+ * unformatted nodes).
+ */
+static int parse_cut_by_coord_range(struct cut40_info *cinfo,
+				    const struct cut_kill_params *params)
+{
+	coord_t *from = params->from;
+	coord_t *to = params->to;
+
+	if (from->item_pos == to->item_pos) {
+		/*
+		 * cut is performed on only one item
+		 */
+		if (from->unit_pos > 0 &&
+		    to->unit_pos < coord_last_unit_pos(to))
+			/*
+			 * cut from the middle of item
+			 */
+			return 1;
+		if (from->unit_pos > 0) {
+			/*
+			 * tail of item is to be cut
+			 */
+			cinfo->tail_removed = params->from->item_pos;
+			cinfo->mode |= CMODE_TAIL;
+		} else if (to->unit_pos < coord_last_unit_pos(to)) {
+			/*
+			 * head of item is to be cut
+			 */
+			cinfo->head_removed = params->from->item_pos;
+			cinfo->mode |= CMODE_HEAD;
+		} else {
+			/*
+			 * item is removed completely
+			 */
+			assert("edward-1631",
+			       from->unit_pos == 0 &&
+			       to->unit_pos == coord_last_unit_pos(to));
+
+			cinfo->first_removed = params->from->item_pos;
+			cinfo->removed_count = 1;
+			cinfo->mode |= CMODE_WHOLE;
+		}
+	} else {
+		cinfo->first_removed = from->item_pos + 1;
+		cinfo->removed_count =
+			to->item_pos - from->item_pos - 1;
 
+		if (from->unit_pos > 0) {
+			/*
+			 * first item is not cut completely
+			 */
+			cinfo->tail_removed = from->item_pos;
+			cinfo->mode |= CMODE_TAIL;
+		} else {
+			cinfo->first_removed--;
+			cinfo->removed_count++;
+		}
+		if (to->unit_pos < coord_last_unit_pos(to)) {
+			/*
+			 * last item is not cut completely
+			 */
+			cinfo->head_removed = to->item_pos;
+			cinfo->mode |= CMODE_HEAD;
+		} else {
+			cinfo->removed_count++;
+		}
+		if (cinfo->removed_count)
+			cinfo->mode |= CMODE_WHOLE;
+	}
 	return 0;
 }
 
+/*
+ * this is used by cut_node40 and kill_node40. It analyses input parameters
+ * and calculates cut mode. There are 2 types of cut. First is when a unit is
+ * removed from the middle of an item.  In this case this function returns 1.
+ * All the rest fits into second case: 0 or 1 of items getting tail cut, 0 or
+ * more items removed completely and 0 or 1 item getting head cut. Function
+ * returns 0 in this case
+ */
+static int parse_cut(struct cut40_info *cinfo,
+		     const struct cut_kill_params *params)
+{
+	init_cinfo(cinfo);
+	if (params->from_key == NULL) {
+		/*
+		 * cut key range is not defined in input parameters
+		 */
+		assert("vs-1513", params->to_key == NULL);
+		return parse_cut_by_coord_range(cinfo, params);
+	} else
+		return parse_cut_by_key_range(cinfo, params);
+}
+
 static void
 call_kill_hooks(znode * node, pos_in_node_t from, pos_in_node_t count,
 		carry_kill_data * kdata)
#1 lore raw

Thank you very much, Edward. I was waiting for this patch a few years. :) I just tested it and seems it fixes the problem with non-deletable directories. I'll test it a week or two and I'll provide feedback about the problem.

Thank you Edward and Ivan for your work, I'm really glad to see activity in development here.

Quoted 1 line · Edward Shishkin
#2 lore raw
In reply to Evgeniy

Thank *you* for the pattern. I used it to narrow down the problem.

Common comments: you have a large number of hash collisions on your partition. It can lead to performance drop. I would recommend to use tea hash in your case. This is not default and should be specified by mkfs option "-o hash=tea_hash" when formatting a partition.

Not an urgent issue, juts FYI.

Thanks,
Edward.

Quoted 9 lines · Evgeniy

Thank you very much, Edward. I was waiting for this patch a few years. :) I just tested it and seems it fixes the problem with non-deletable directories. I'll test it a week or two and I'll provide feedback about the problem.

Thank you Edward and Ivan for your work, I'm really glad to see activity in development here.

On 26 September 2014 23:01, Edward Shishkin <[email protected]> wrote: