lustre/nodemap/nodemap_idmap.c

   1 /*
   2  * GPL HEADER START
   3  *
   4  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License version 2 only,
   8  * as published by the Free Software Foundation.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * General Public License version 2 for more details (a copy is included
  14  * in the LICENSE file that accompanied this code).
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * version 2 along with this program; If not, see
  18  * http://www.gnu.org/licenses/gpl-2.0.html
  19  *
  20  * GPL HEADER END
  21  */
  22 /*
  23  * Copyright (C) 2013, Trustees of Indiana University
  24  * Author: Joshua Walgenbach <jjw@iu.edu>
  25  */
  26
  27 #include <linux/rbtree.h>
  28 #include <lustre_net.h>
  29 #include "nodemap_internal.h"
  30
  31 /**
  32  * allocate the lu_idmap structure
  33  *
  34  * \param       client_id               client uid or gid
  35  * \param       fs_id                   filesystem uid or gid
  36  *
  37  * \retval      alloated lu_idmap structure on success, NULL otherwise
  38  */
  39 struct lu_idmap *idmap_create(__u32 client_id, __u32 fs_id)
  40 {
  41         struct lu_idmap *idmap;
  42
  43         OBD_ALLOC_PTR(idmap);
  44         if (idmap == NULL) {
  45                 CERROR("cannot allocate lu_idmap of size %zu bytes\n",
  46                        sizeof(idmap));
  47                 return NULL;
  48         }
  49
  50         idmap->id_client = client_id;
  51         idmap->id_fs = fs_id;
  52         RB_CLEAR_NODE(&idmap->id_client_to_fs);
  53         RB_CLEAR_NODE(&idmap->id_fs_to_client);
  54         return idmap;
  55 }
  56
  57 static void idmap_destroy(struct lu_idmap *idmap)
  58
  59 {
  60         LASSERT(RB_EMPTY_NODE(&idmap->id_fs_to_client) == 0);
  61         LASSERT(RB_EMPTY_NODE(&idmap->id_client_to_fs) == 0);
  62         OBD_FREE_PTR(idmap);
  63 }
  64
  65 /**
  66  * insert idmap into the proper trees
  67  *
  68  * \param       node_type               0 for UID
  69  *                                      1 for GID
  70  * \param       idmap                   lu_idmap structure to insert
  71  * \param       nodemap                 nodemap to associate with the map
  72  *
  73  * \retval      0 on success
  74  *
  75  * if the mapping exists, this function will delete it and replace
  76  * it with the new idmap structure
  77  */
  78 void idmap_insert(enum nodemap_id_type id_type, struct lu_idmap *idmap,
  79                  struct lu_nodemap *nodemap)
  80 {
  81         struct lu_idmap         *cur = NULL;
  82         struct rb_node          *fwd_parent = NULL;
  83         struct rb_node          *bck_parent = NULL;
  84         struct rb_node          **fwd_node;
  85         struct rb_node          **bck_node;
  86         struct rb_root          *fwd_root;
  87         struct rb_root          *bck_root;
  88         bool                    replace = false;
  89
  90         /* for purposes in idmap client to fs is forward
  91          * mapping, fs to client is backward mapping
  92          */
  93         if (id_type == NODEMAP_UID) {
  94                 fwd_root = &nodemap->nm_client_to_fs_uidmap;
  95                 bck_root = &nodemap->nm_fs_to_client_uidmap;
  96         } else {
  97                 fwd_root = &nodemap->nm_client_to_fs_gidmap;
  98                 bck_root = &nodemap->nm_fs_to_client_gidmap;
  99         }
 100
 101         fwd_node = &fwd_root->rb_node;
 102         bck_node = &bck_root->rb_node;
 103
 104         /* find fwd and bck idmap nodes before insertion or
 105          * replacing to precent split brain idmaps
 106          */
 107         while (*fwd_node) {
 108                 cur = rb_entry(*fwd_node, struct lu_idmap,
 109                                id_client_to_fs);
 110
 111                 if (idmap->id_client < cur->id_client) {
 112                         fwd_node = &((*fwd_node)->rb_left);
 113                 } else if (idmap->id_client > cur->id_client) {
 114                         fwd_node = &((*fwd_node)->rb_right);
 115                 } else {
 116                         replace = true;
 117                         break;
 118                 }
 119
 120                 fwd_parent = *fwd_node;
 121         }
 122
 123         if (!replace) {
 124                 while (*bck_node) {
 125                         cur = rb_entry(*bck_node, struct lu_idmap,
 126                                        id_fs_to_client);
 127
 128                         if (idmap->id_fs < cur->id_fs) {
 129                                 bck_node = &((*bck_node)->rb_left);
 130                         } else if (idmap->id_fs > cur->id_fs) {
 131                                 bck_node = &((*bck_node)->rb_right);
 132                         } else {
 133                                 replace = true;
 134                                 break;
 135                         }
 136
 137                         bck_parent = *bck_node;
 138                 }
 139         }
 140
 141         if (!replace) {
 142                 rb_link_node(&idmap->id_client_to_fs, fwd_parent, fwd_node);
 143                 rb_insert_color(&idmap->id_client_to_fs, fwd_root);
 144                 rb_link_node(&idmap->id_fs_to_client, bck_parent, bck_node);
 145                 rb_insert_color(&idmap->id_fs_to_client, bck_root);
 146         } else {
 147                 rb_replace_node(&cur->id_client_to_fs,
 148                                 &idmap->id_client_to_fs,
 149                                 fwd_root);
 150                 rb_replace_node(&cur->id_fs_to_client,
 151                                 &idmap->id_fs_to_client,
 152                                 bck_root);
 153
 154                 idmap_destroy(cur);
 155         }
 156 }
 157
 158 /**
 159  * delete idmap from the correct nodemap tree
 160  *
 161  * \param       node_type               0 for UID
 162  *                                      1 for GID
 163  * \param       idmap                   idmap to delete
 164  * \param       nodemap                 assoicated idmap
 165  */
 166 void idmap_delete(enum nodemap_id_type id_type, struct lu_idmap *idmap,
 167                   struct lu_nodemap *nodemap)
 168 {
 169         struct rb_root  *fwd_root;
 170         struct rb_root  *bck_root;
 171
 172         if (id_type == NODEMAP_UID) {
 173                 fwd_root = &nodemap->nm_client_to_fs_uidmap;
 174                 bck_root = &nodemap->nm_fs_to_client_uidmap;
 175         } else {
 176                 fwd_root = &nodemap->nm_client_to_fs_gidmap;
 177                 bck_root = &nodemap->nm_fs_to_client_gidmap;
 178         }
 179
 180         rb_erase(&idmap->id_client_to_fs, fwd_root);
 181         rb_erase(&idmap->id_fs_to_client, bck_root);
 182
 183         idmap_destroy(idmap);
 184 }
 185
 186 /**
 187  * search for an existing id in the nodemap trees
 188  *
 189  * \param       nodemap         nodemap trees to search
 190  * \param       tree_type       0 for filesystem to client maps
 191  *                              1 for client to filesystem maps
 192  * \param       id_type         0 for UID
 193  *                              1 for GID
 194  * \param       id              numeric id for which to search
 195  *
 196  * \retval      lu_idmap structure with the map on success
 197  */
 198 struct lu_idmap *idmap_search(struct lu_nodemap *nodemap,
 199                               enum nodemap_tree_type tree_type,
 200                               enum nodemap_id_type id_type,
 201                               const __u32 id)
 202 {
 203         struct rb_node  *node;
 204         struct rb_root  *root = NULL;
 205         struct lu_idmap *idmap;
 206
 207         if (id_type == NODEMAP_UID && tree_type == NODEMAP_FS_TO_CLIENT)
 208                 root = &nodemap->nm_fs_to_client_uidmap;
 209         else if (id_type == NODEMAP_UID && tree_type == NODEMAP_CLIENT_TO_FS)
 210                 root = &nodemap->nm_client_to_fs_uidmap;
 211         else if (id_type == NODEMAP_GID && tree_type == NODEMAP_FS_TO_CLIENT)
 212                 root = &nodemap->nm_fs_to_client_gidmap;
 213         else if (id_type == NODEMAP_GID && tree_type == NODEMAP_CLIENT_TO_FS)
 214                 root = &nodemap->nm_client_to_fs_gidmap;
 215
 216         node = root->rb_node;
 217
 218         if (tree_type == NODEMAP_FS_TO_CLIENT) {
 219                 while (node) {
 220                         idmap = rb_entry(node, struct lu_idmap,
 221                                          id_fs_to_client);
 222                         if (id < idmap->id_fs)
 223                                 node = node->rb_left;
 224                         else if (id > idmap->id_fs)
 225                                 node = node->rb_right;
 226                         else
 227                                 return idmap;
 228                 }
 229         } else {
 230                 while (node) {
 231                         idmap = rb_entry(node, struct lu_idmap,
 232                                          id_client_to_fs);
 233                         if (id < idmap->id_client)
 234                                 node = node->rb_left;
 235                         else if (id > idmap->id_client)
 236                                 node = node->rb_right;
 237                         else
 238                                 return idmap;
 239                 }
 240         }
 241
 242         return NULL;
 243 }
 244
 245 /*
 246  * delete all idmap trees from a nodemap
 247  *
 248  * \param       nodemap         nodemap to delete trees from
 249  *
 250  * This uses the postorder safe traversal code that is commited
 251  * in a later kernel. Each lu_idmap strucuture is destroyed.
 252  */
 253 void idmap_delete_tree(struct lu_nodemap *nodemap)
 254 {
 255         struct lu_idmap         *idmap;
 256         struct lu_idmap         *temp;
 257         struct rb_root          root;
 258
 259         root = nodemap->nm_fs_to_client_uidmap;
 260         nm_rbtree_postorder_for_each_entry_safe(idmap, temp, &root,
 261                                                 id_fs_to_client) {
 262                 idmap_destroy(idmap);
 263         }
 264
 265         root = nodemap->nm_client_to_fs_gidmap;
 266         nm_rbtree_postorder_for_each_entry_safe(idmap, temp, &root,
 267                                                 id_client_to_fs) {
 268                 idmap_destroy(idmap);
 269         }
 270 }