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