xref: /freebsd-src/sys/contrib/openzfs/module/zfs/objlist.c (revision e25152834cdf3b353892835a4f3b157e066a8ed4)
1*eda14cbcSMatt Macy /*
2*eda14cbcSMatt Macy  * CDDL HEADER START
3*eda14cbcSMatt Macy  *
4*eda14cbcSMatt Macy  * This file and its contents are supplied under the terms of the
5*eda14cbcSMatt Macy  * Common Development and Distribution License ("CDDL"), version 1.0.
6*eda14cbcSMatt Macy  * You may only use this file in accordance with the terms of version
7*eda14cbcSMatt Macy  * 1.0 of the CDDL.
8*eda14cbcSMatt Macy  *
9*eda14cbcSMatt Macy  * A full copy of the text of the CDDL should have accompanied this
10*eda14cbcSMatt Macy  * source.  A copy of the CDDL is also available via the Internet at
11*eda14cbcSMatt Macy  * http://www.illumos.org/license/CDDL.
12*eda14cbcSMatt Macy  *
13*eda14cbcSMatt Macy  * CDDL HEADER END
14*eda14cbcSMatt Macy  */
15*eda14cbcSMatt Macy /*
16*eda14cbcSMatt Macy  * Copyright (c) 2018 by Delphix. All rights reserved.
17*eda14cbcSMatt Macy  */
18*eda14cbcSMatt Macy 
19*eda14cbcSMatt Macy #include	<sys/objlist.h>
20*eda14cbcSMatt Macy #include	<sys/zfs_context.h>
21*eda14cbcSMatt Macy 
22*eda14cbcSMatt Macy objlist_t *
objlist_create(void)23*eda14cbcSMatt Macy objlist_create(void)
24*eda14cbcSMatt Macy {
25*eda14cbcSMatt Macy 	objlist_t *list = kmem_alloc(sizeof (*list), KM_SLEEP);
26*eda14cbcSMatt Macy 	list_create(&list->ol_list, sizeof (objlist_node_t),
27*eda14cbcSMatt Macy 	    offsetof(objlist_node_t, on_node));
28*eda14cbcSMatt Macy 	list->ol_last_lookup = 0;
29*eda14cbcSMatt Macy 	return (list);
30*eda14cbcSMatt Macy }
31*eda14cbcSMatt Macy 
32*eda14cbcSMatt Macy void
objlist_destroy(objlist_t * list)33*eda14cbcSMatt Macy objlist_destroy(objlist_t *list)
34*eda14cbcSMatt Macy {
35*eda14cbcSMatt Macy 	for (objlist_node_t *n = list_remove_head(&list->ol_list);
36*eda14cbcSMatt Macy 	    n != NULL; n = list_remove_head(&list->ol_list)) {
37*eda14cbcSMatt Macy 		kmem_free(n, sizeof (*n));
38*eda14cbcSMatt Macy 	}
39*eda14cbcSMatt Macy 	list_destroy(&list->ol_list);
40*eda14cbcSMatt Macy 	kmem_free(list, sizeof (*list));
41*eda14cbcSMatt Macy }
42*eda14cbcSMatt Macy 
43*eda14cbcSMatt Macy /*
44*eda14cbcSMatt Macy  * This function looks through the objlist to see if the specified object number
45*eda14cbcSMatt Macy  * is contained in the objlist.  In the process, it will remove all object
46*eda14cbcSMatt Macy  * numbers in the list that are smaller than the specified object number.  Thus,
47*eda14cbcSMatt Macy  * any lookup of an object number smaller than a previously looked up object
48*eda14cbcSMatt Macy  * number will always return false; therefore, all lookups should be done in
49*eda14cbcSMatt Macy  * ascending order.
50*eda14cbcSMatt Macy  */
51*eda14cbcSMatt Macy boolean_t
objlist_exists(objlist_t * list,uint64_t object)52*eda14cbcSMatt Macy objlist_exists(objlist_t *list, uint64_t object)
53*eda14cbcSMatt Macy {
54*eda14cbcSMatt Macy 	objlist_node_t *node = list_head(&list->ol_list);
55*eda14cbcSMatt Macy 	ASSERT3U(object, >=, list->ol_last_lookup);
56*eda14cbcSMatt Macy 	list->ol_last_lookup = object;
57*eda14cbcSMatt Macy 	while (node != NULL && node->on_object < object) {
58*eda14cbcSMatt Macy 		VERIFY3P(node, ==, list_remove_head(&list->ol_list));
59*eda14cbcSMatt Macy 		kmem_free(node, sizeof (*node));
60*eda14cbcSMatt Macy 		node = list_head(&list->ol_list);
61*eda14cbcSMatt Macy 	}
62*eda14cbcSMatt Macy 	return (node != NULL && node->on_object == object);
63*eda14cbcSMatt Macy }
64*eda14cbcSMatt Macy 
65*eda14cbcSMatt Macy /*
66*eda14cbcSMatt Macy  * The objlist is a list of object numbers stored in ascending order.  However,
67*eda14cbcSMatt Macy  * the insertion of new object numbers does not seek out the correct location to
68*eda14cbcSMatt Macy  * store a new object number; instead, it appends it to the list for simplicity.
69*eda14cbcSMatt Macy  * Thus, any users must take care to only insert new object numbers in ascending
70*eda14cbcSMatt Macy  * order.
71*eda14cbcSMatt Macy  */
72*eda14cbcSMatt Macy void
objlist_insert(objlist_t * list,uint64_t object)73*eda14cbcSMatt Macy objlist_insert(objlist_t *list, uint64_t object)
74*eda14cbcSMatt Macy {
75*eda14cbcSMatt Macy 	objlist_node_t *node = kmem_zalloc(sizeof (*node), KM_SLEEP);
76*eda14cbcSMatt Macy 	node->on_object = object;
77*eda14cbcSMatt Macy #ifdef ZFS_DEBUG
78*eda14cbcSMatt Macy 	objlist_node_t *last_object = list_tail(&list->ol_list);
79*eda14cbcSMatt Macy 	uint64_t last_objnum = (last_object != NULL ? last_object->on_object :
80*eda14cbcSMatt Macy 	    0);
81*eda14cbcSMatt Macy 	ASSERT3U(node->on_object, >, last_objnum);
82*eda14cbcSMatt Macy #endif
83*eda14cbcSMatt Macy 	list_insert_tail(&list->ol_list, node);
84*eda14cbcSMatt Macy }
85