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       id_type         NODEMAP_UID or NODEMAP_GID
  69  * \param       idmap           lu_idmap structure to insert
  70  * \param       nodemap         nodemap to associate with the map
  71  *
  72  * \retval      NULL             on success
  73  * \retval      ERR_PTR(-EEXIST) if this idmap already exists
  74  * \retval      struct lu_idmap  if only id_client or id_fs of this idmap
  75  *                               is matched, return the matched idmap.
  76  *                               The caller will delete this old idmap and
  77  *                               its index before insert the new idmap again.
  78  */
  79 struct lu_idmap *idmap_insert(enum nodemap_id_type id_type,
  80                               struct lu_idmap *idmap,
  81                               struct lu_nodemap *nodemap)
  82 {
  83         struct lu_idmap         *fwd_cur = NULL;
  84         struct lu_idmap         *bck_cur = NULL;
  85         struct rb_node          *fwd_parent = NULL;
  86         struct rb_node          *bck_parent = NULL;
  87         struct rb_node          **fwd_node;
  88         struct rb_node          **bck_node;
  89         struct rb_root          *fwd_root;
  90         struct rb_root          *bck_root;
  91         bool                    fwd_found = false;
  92         bool                    bck_found = false;
  93
  94         ENTRY;
  95
  96         /* for purposes in idmap client to fs is forward
  97          * mapping, fs to client is backward mapping
  98          */
  99         if (id_type == NODEMAP_UID) {
 100                 fwd_root = &nodemap->nm_client_to_fs_uidmap;
 101                 bck_root = &nodemap->nm_fs_to_client_uidmap;
 102         } else {
 103                 fwd_root = &nodemap->nm_client_to_fs_gidmap;
 104                 bck_root = &nodemap->nm_fs_to_client_gidmap;
 105         }
 106
 107         fwd_node = &fwd_root->rb_node;
 108         bck_node = &bck_root->rb_node;
 109
 110         /* find fwd and bck idmap nodes before insertion or
 111          * replacing to prevent split brain idmaps
 112          */
 113         while (*fwd_node) {
 114                 fwd_parent = *fwd_node;
 115                 fwd_cur = rb_entry(*fwd_node, struct lu_idmap,
 116                                    id_client_to_fs);
 117
 118                 if (idmap->id_client < fwd_cur->id_client) {
 119                         fwd_node = &((*fwd_node)->rb_left);
 120                 } else if (idmap->id_client > fwd_cur->id_client) {
 121                         fwd_node = &((*fwd_node)->rb_right);
 122                 } else {
 123                         fwd_found = true;
 124                         break;
 125                 }
 126         }
 127
 128         while (*bck_node) {
 129                 bck_parent = *bck_node;
 130                 bck_cur = rb_entry(*bck_node, struct lu_idmap,
 131                                    id_fs_to_client);
 132
 133                 if (idmap->id_fs < bck_cur->id_fs) {
 134                         bck_node = &((*bck_node)->rb_left);
 135                 } else if (idmap->id_fs > bck_cur->id_fs) {
 136                         bck_node = &((*bck_node)->rb_right);
 137                 } else {
 138                         bck_found = true;
 139                         break;
 140                 }
 141         }
 142
 143         /* Already exists */
 144         if (fwd_found && bck_found)
 145                 RETURN(ERR_PTR(-EEXIST));
 146
 147         /* Insert a new idmap */
 148         if (!fwd_found && !bck_found) {
 149                 CDEBUG(D_INFO, "Insert a new idmap %d:%d\n",
 150                        idmap->id_client, idmap->id_fs);
 151                 rb_link_node(&idmap->id_client_to_fs, fwd_parent, fwd_node);
 152                 rb_insert_color(&idmap->id_client_to_fs, fwd_root);
 153                 rb_link_node(&idmap->id_fs_to_client, bck_parent, bck_node);
 154                 rb_insert_color(&idmap->id_fs_to_client, bck_root);
 155                 RETURN(NULL);
 156         }
 157
 158         /* Only id_client or id_fs is matched */
 159         RETURN(fwd_found ? fwd_cur : bck_cur);
 160 }
 161
 162 /**
 163  * Delete idmap from the correct nodemap tree
 164  *
 165  * \param       node_type               0 for UID
 166  *                                      1 for GID
 167  * \param       idmap                   idmap to delete
 168  * \param       nodemap                 assoicated idmap
 169  */
 170 void idmap_delete(enum nodemap_id_type id_type, struct lu_idmap *idmap,
 171                   struct lu_nodemap *nodemap)
 172 {
 173         struct rb_root  *fwd_root;
 174         struct rb_root  *bck_root;
 175
 176         if (id_type == NODEMAP_UID) {
 177                 fwd_root = &nodemap->nm_client_to_fs_uidmap;
 178                 bck_root = &nodemap->nm_fs_to_client_uidmap;
 179         } else {
 180                 fwd_root = &nodemap->nm_client_to_fs_gidmap;
 181                 bck_root = &nodemap->nm_fs_to_client_gidmap;
 182         }
 183
 184         rb_erase(&idmap->id_client_to_fs, fwd_root);
 185         rb_erase(&idmap->id_fs_to_client, bck_root);
 186
 187         idmap_destroy(idmap);
 188 }
 189
 190 /**
 191  * Search for an existing id in the nodemap trees.
 192  *
 193  * \param       nodemap         nodemap trees to search
 194  * \param       tree_type       0 for filesystem to client maps
 195  *                              1 for client to filesystem maps
 196  * \param       id_type         0 for UID
 197  *                              1 for GID
 198  * \param       id              numeric id for which to search
 199  *
 200  * \retval      lu_idmap structure with the map on success
 201  */
 202 struct lu_idmap *idmap_search(struct lu_nodemap *nodemap,
 203                               enum nodemap_tree_type tree_type,
 204                               enum nodemap_id_type id_type,
 205                               const __u32 id)
 206 {
 207         struct rb_node  *node;
 208         struct rb_root  *root = NULL;
 209         struct lu_idmap *idmap;
 210
 211         ENTRY;
 212
 213         if (id_type == NODEMAP_UID && tree_type == NODEMAP_FS_TO_CLIENT)
 214                 root = &nodemap->nm_fs_to_client_uidmap;
 215         else if (id_type == NODEMAP_UID && tree_type == NODEMAP_CLIENT_TO_FS)
 216                 root = &nodemap->nm_client_to_fs_uidmap;
 217         else if (id_type == NODEMAP_GID && tree_type == NODEMAP_FS_TO_CLIENT)
 218                 root = &nodemap->nm_fs_to_client_gidmap;
 219         else if (id_type == NODEMAP_GID && tree_type == NODEMAP_CLIENT_TO_FS)
 220                 root = &nodemap->nm_client_to_fs_gidmap;
 221
 222         node = root->rb_node;
 223
 224         if (tree_type == NODEMAP_FS_TO_CLIENT) {
 225                 while (node) {
 226                         idmap = rb_entry(node, struct lu_idmap,
 227                                          id_fs_to_client);
 228                         if (id < idmap->id_fs)
 229                                 node = node->rb_left;
 230                         else if (id > idmap->id_fs)
 231                                 node = node->rb_right;
 232                         else
 233                                 RETURN(idmap);
 234                 }
 235         } else {
 236                 while (node) {
 237                         idmap = rb_entry(node, struct lu_idmap,
 238                                          id_client_to_fs);
 239                         if (id < idmap->id_client)
 240                                 node = node->rb_left;
 241                         else if (id > idmap->id_client)
 242                                 node = node->rb_right;
 243                         else
 244                                 RETURN(idmap);
 245                 }
 246         }
 247
 248         RETURN(NULL);
 249 }
 250
 251 /*
 252  * delete all idmap trees from a nodemap
 253  *
 254  * \param       nodemap         nodemap to delete trees from
 255  *
 256  * This uses the postorder safe traversal code that is committed
 257  * in a later kernel. Each lu_idmap strucuture is destroyed.
 258  */
 259 void idmap_delete_tree(struct lu_nodemap *nodemap)
 260 {
 261         struct lu_idmap         *idmap;
 262         struct lu_idmap         *temp;
 263         struct rb_root          root;
 264
 265         root = nodemap->nm_fs_to_client_uidmap;
 266         nm_rbtree_postorder_for_each_entry_safe(idmap, temp, &root,
 267                                                 id_fs_to_client) {
 268                 idmap_destroy(idmap);
 269         }
 270
 271         root = nodemap->nm_client_to_fs_gidmap;
 272         nm_rbtree_postorder_for_each_entry_safe(idmap, temp, &root,
 273                                                 id_client_to_fs) {
 274                 idmap_destroy(idmap);
 275         }
 276 }