fs/ceph/inode.c

245  * We use a 'frag tree' to keep track of the MDS's directory fragments
247  * need to know when a child frag is delegated to a new MDS, or when
253  * find/create a frag in the tree
262 	struct ceph_inode_frag *frag;
268 		frag = rb_entry(parent, struct ceph_inode_frag, node);
269 		c = ceph_frag_compare(f, frag->frag);
275 			return frag;
278 	frag = kmalloc(sizeof(*frag), GFP_NOFS);
279 	if (!frag)
282 	frag->frag = f;
283 	frag->split_by = 0;
284 	frag->mds = -1;
285 	frag->ndist = 0;
287 	rb_link_node(&frag->node, parent, p);
288 	rb_insert_color(&frag->node, &ci->i_fragtree);
290 	doutc(cl, "added %p %llx.%llx frag %x\n", inode, ceph_vinop(inode), f);
291 	return frag;
295  * find a specific frag @f
302 		struct ceph_inode_frag *frag =
304 		int c = ceph_frag_compare(f, frag->frag);
310 			return frag;
316  * Choose frag containing the given value @v.  If @pfrag is
317  * specified, copy the frag delegation info to the caller if
325 	struct ceph_inode_frag *frag;
334 		frag = __ceph_find_frag(ci, t);
335 		if (!frag)
337 		if (frag->split_by == 0) {
339 				memcpy(pfrag, frag, sizeof(*pfrag));
346 		nway = 1 << frag->split_by;
347 		doutc(cl, "frag(%x) %x splits by %d (%d ways)\n", v, t,
348 		      frag->split_by, nway);
350 			n = ceph_frag_make_child(t, frag->split_by, i);
358 	doutc(cl, "frag(%x) = %x\n", v, t);
383 	struct ceph_inode_frag *frag;
384 	u32 id = le32_to_cpu(dirinfo->frag);
402 		frag = __ceph_find_frag(ci, id);
403 		if (!frag)
405 		if (frag->split_by == 0) {
407 			doutc(cl, "removed %p %llx.%llx frag %x (no ref)\n",
409 			rb_erase(&frag->node, &ci->i_fragtree);
410 			kfree(frag);
413 			doutc(cl, "cleared %p %llx.%llx frag %x referral\n",
415 			frag->mds = -1;
416 			frag->ndist = 0;
422 	/* find/add this frag to store mds delegation info */
423 	frag = __get_or_create_frag(ci, id);
424 	if (IS_ERR(frag)) {
429 			      le32_to_cpu(dirinfo->frag));
434 	frag->mds = mds;
435 	frag->ndist = min_t(u32, ndist, CEPH_MAX_DIRFRAG_REP);
436 	for (i = 0; i < frag->ndist; i++)
437 		frag->dist[i] = le32_to_cpu(dirinfo->dist[i]);
438 	doutc(cl, "%p %llx.%llx frag %x ndist=%d\n", inode,
439 	      ceph_vinop(inode), frag->frag, frag->ndist);
450 	return ceph_frag_compare(le32_to_cpu(ls->frag),
451 				 le32_to_cpu(rs->frag));
454 static bool is_frag_child(u32 f, struct ceph_inode_frag *frag)
456 	if (!frag)
458 	if (ceph_frag_bits(f) != ceph_frag_bits(frag->frag) + frag->split_by)
460 	return ceph_frag_contains_value(frag->frag, ceph_frag_value(f));
469 	struct ceph_inode_frag *frag, *prev_frag = NULL;
481 		id = le32_to_cpu(fragtree->splits[i].frag);
486 		frag = rb_entry(rb_node, struct ceph_inode_frag, node);
487 		if (frag->frag != ceph_frag_make(0, 0) || rb_next(rb_node))
491 		id = le32_to_cpu(dirinfo->frag);
506 		id = le32_to_cpu(fragtree->splits[i].frag);
510 			       "frag %x split by %d\n", inode,
514 		frag = NULL;
516 			frag = rb_entry(rb_node, struct ceph_inode_frag, node);
517 			if (ceph_frag_compare(frag->frag, id) >= 0) {
518 				if (frag->frag != id)
519 					frag = NULL;
526 			if (frag->split_by > 0 ||
527 			    !is_frag_child(frag->frag, prev_frag)) {
528 				rb_erase(&frag->node, &ci->i_fragtree);
529 				if (frag->split_by > 0)
531 				kfree(frag);
533 			frag = NULL;
535 		if (!frag) {
536 			frag = __get_or_create_frag(ci, id);
537 			if (IS_ERR(frag))
540 		if (frag->split_by == 0)
542 		frag->split_by = split_by;
543 		doutc(cl, " frag %x split by %d\n", frag->frag, frag->split_by);
544 		prev_frag = frag;
547 		frag = rb_entry(rb_node, struct ceph_inode_frag, node);
550 		if (frag->split_by > 0 ||
551 		    !is_frag_child(frag->frag, prev_frag)) {
552 			rb_erase(&frag->node, &ci->i_fragtree);
553 			if (frag->split_by > 0)
555 			kfree(frag);
691 	struct ceph_inode_frag *frag;
727 		frag = rb_entry(n, struct ceph_inode_frag, node);
729 		kfree(frag);
1320 	/* populate frag tree */
1906 	u32 frag = le32_to_cpu(req->r_args.readdir.frag);
1928 	    le32_to_cpu(rinfo->dir_dir->frag) != frag) {
1929 		doutc(cl, "got new frag %x -> %x\n", frag,
1930 			    le32_to_cpu(rinfo->dir_dir->frag));
1931 		frag = le32_to_cpu(rinfo->dir_dir->frag);
1944 		if (ceph_frag_is_leftmost(frag) &&
1979 			rde->offset = ceph_make_fpos(frag, fpos_offset++, false);