sys/contrib/openzfs/module/zfs/objlist.c

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