lustre/ptlrpc/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 prevent split brain idmaps
 106          */
 107         while (*fwd_node) {
 108                 fwd_parent = *fwd_node;
 109                 cur = rb_entry(*fwd_node, struct lu_idmap,
 110                                id_client_to_fs);
 111
 112                 if (idmap->id_client < cur->id_client) {
 113                         fwd_node = &((*fwd_node)->rb_left);
 114                 } else if (idmap->id_client > cur->id_client) {
 115                         fwd_node = &((*fwd_node)->rb_right);
 116                 } else {
 117                         replace = true;
 118                         break;
 119                 }
 120         }
 121
 122         if (!replace) {
 123                 while (*bck_node) {
 124                         bck_parent = *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         }
 138
 139         if (!replace) {
 140                 rb_link_node(&idmap->id_client_to_fs, fwd_parent, fwd_node);
 141                 rb_insert_color(&idmap->id_client_to_fs, fwd_root);
 142                 rb_link_node(&idmap->id_fs_to_client, bck_parent, bck_node);
 143                 rb_insert_color(&idmap->id_fs_to_client, bck_root);
 144         } else {
 145                 rb_replace_node(&cur->id_client_to_fs,
 146                                 &idmap->id_client_to_fs,
 147                                 fwd_root);
 148                 rb_replace_node(&cur->id_fs_to_client,
 149                                 &idmap->id_fs_to_client,
 150                                 bck_root);
 151
 152                 idmap_destroy(cur);
 153         }
 154 }
 155
 156 /**
 157  * Delete idmap from the correct nodemap tree
 158  *
 159  * \param       node_type               0 for UID
 160  *                                      1 for GID
 161  * \param       idmap                   idmap to delete
 162  * \param       nodemap                 assoicated idmap
 163  */
 164 void idmap_delete(enum nodemap_id_type id_type, struct lu_idmap *idmap,
 165                   struct lu_nodemap *nodemap)
 166 {
 167         struct rb_root  *fwd_root;
 168         struct rb_root  *bck_root;
 169
 170         if (id_type == NODEMAP_UID) {
 171                 fwd_root = &nodemap->nm_client_to_fs_uidmap;
 172                 bck_root = &nodemap->nm_fs_to_client_uidmap;
 173         } else {
 174                 fwd_root = &nodemap->nm_client_to_fs_gidmap;
 175                 bck_root = &nodemap->nm_fs_to_client_gidmap;
 176         }
 177
 178         rb_erase(&idmap->id_client_to_fs, fwd_root);
 179         rb_erase(&idmap->id_fs_to_client, bck_root);
 180
 181         idmap_destroy(idmap);
 182 }
 183
 184 /**
 185  * Search for an existing id in the nodemap trees.
 186  *
 187  * \param       nodemap         nodemap trees to search
 188  * \param       tree_type       0 for filesystem to client maps
 189  *                              1 for client to filesystem maps
 190  * \param       id_type         0 for UID
 191  *                              1 for GID
 192  * \param       id              numeric id for which to search
 193  *
 194  * \retval      lu_idmap structure with the map on success
 195  */
 196 struct lu_idmap *idmap_search(struct lu_nodemap *nodemap,
 197                               enum nodemap_tree_type tree_type,
 198                               enum nodemap_id_type id_type,
 199                               const __u32 id)
 200 {
 201         struct rb_node  *node;
 202         struct rb_root  *root = NULL;
 203         struct lu_idmap *idmap;
 204
 205         if (id_type == NODEMAP_UID && tree_type == NODEMAP_FS_TO_CLIENT)
 206                 root = &nodemap->nm_fs_to_client_uidmap;
 207         else if (id_type == NODEMAP_UID && tree_type == NODEMAP_CLIENT_TO_FS)
 208                 root = &nodemap->nm_client_to_fs_uidmap;
 209         else if (id_type == NODEMAP_GID && tree_type == NODEMAP_FS_TO_CLIENT)
 210                 root = &nodemap->nm_fs_to_client_gidmap;
 211         else if (id_type == NODEMAP_GID && tree_type == NODEMAP_CLIENT_TO_FS)
 212                 root = &nodemap->nm_client_to_fs_gidmap;
 213
 214         node = root->rb_node;
 215
 216         if (tree_type == NODEMAP_FS_TO_CLIENT) {
 217                 while (node) {
 218                         idmap = rb_entry(node, struct lu_idmap,
 219                                          id_fs_to_client);
 220                         if (id < idmap->id_fs)
 221                                 node = node->rb_left;
 222                         else if (id > idmap->id_fs)
 223                                 node = node->rb_right;
 224                         else
 225                                 return idmap;
 226                 }
 227         } else {
 228                 while (node) {
 229                         idmap = rb_entry(node, struct lu_idmap,
 230                                          id_client_to_fs);
 231                         if (id < idmap->id_client)
 232                                 node = node->rb_left;
 233                         else if (id > idmap->id_client)
 234                                 node = node->rb_right;
 235                         else
 236                                 return idmap;
 237                 }
 238         }
 239
 240         return NULL;
 241 }
 242
 243 /*
 244  * delete all idmap trees from a nodemap
 245  *
 246  * \param       nodemap         nodemap to delete trees from
 247  *
 248  * This uses the postorder safe traversal code that is commited
 249  * in a later kernel. Each lu_idmap strucuture is destroyed.
 250  */
 251 void idmap_delete_tree(struct lu_nodemap *nodemap)
 252 {
 253         struct lu_idmap         *idmap;
 254         struct lu_idmap         *temp;
 255         struct rb_root          root;
 256
 257         root = nodemap->nm_fs_to_client_uidmap;
 258         nm_rbtree_postorder_for_each_entry_safe(idmap, temp, &root,
 259                                                 id_fs_to_client) {
 260                 idmap_destroy(idmap);
 261         }
 262
 263         root = nodemap->nm_client_to_fs_gidmap;
 264         nm_rbtree_postorder_for_each_entry_safe(idmap, temp, &root,
 265                                                 id_client_to_fs) {
 266                 idmap_destroy(idmap);
 267         }
 268 }