src/afb-perm.c

   1 /*
   2  * Copyright (C) 2017 "IoT.bzh"
   3  * Author José Bollo <jose.bollo@iot.bzh>
   4  *
   5  * Licensed under the Apache License, Version 2.0 (the "License");
   6  * you may not use this file except in compliance with the License.
   7  * You may obtain a copy of the License at
   8  *
   9  *   http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18
  19 #include <stdlib.h>
  20 #include <assert.h>
  21 #include <string.h>
  22 #include <errno.h>
  23 #include <ctype.h>
  24
  25 #include "afb-perm.h"
  26 #include "verbose.h"
  27
  28 /*********************************************************************
  29 *** SECTION node
  30 *********************************************************************/
  31
  32 /**
  33  * types of nodes
  34  */
  35 enum type
  36 {
  37         Text,   /**< text node */
  38         And,    /**< and node */
  39         Or,     /**< or node */
  40         Not     /**< not node */
  41 };
  42
  43 /**
  44  * structure for nodes
  45  */
  46 struct node
  47 {
  48         enum type type; /**< type of the node */
  49         union {
  50                 struct node *children[2]; /**< possible subnodes */
  51                 char text[1]; /**< text of the node */
  52         };
  53 };
  54
  55 /**
  56  * make a text node and return it
  57  * @param type type of the node (should be Text)
  58  * @param text the text to set for the node
  59  * @param length the length of the text
  60  * @return the allocated node or NULL on memory depletion
  61  */
  62 static struct node *node_make_text(enum type type, const char *text, size_t length)
  63 {
  64         struct node *node;
  65
  66         node = malloc(length + sizeof *node);
  67         if (!node)
  68                 errno = ENOMEM;
  69         else {
  70                 node->type = type;
  71                 memcpy(node->text, text, length);
  72                 node->text[length] = 0;
  73         }
  74         return node;
  75 }
  76
  77 /**
  78  * make a node with sub nodes and return it
  79  * @param type type of the node (should be And, Or or Text)
  80  * @param left the "left" sub node
  81  * @param right the "right" sub node (if any or NULL)
  82  * @return the allocated node or NULL on memory depletion
  83  */
  84 static struct node *node_make_parent(enum type type, struct node *left, struct node *right)
  85 {
  86         struct node *node;
  87
  88         node = malloc(sizeof *node);
  89         if (!node)
  90                 errno = ENOMEM;
  91         else {
  92                 node->type = type;
  93                 node->children[0] = left;
  94                 node->children[1] = right;
  95         }
  96         return node;
  97 }
  98
  99 /**
 100  * Frees the node and its possible subnodes
 101  * @param node the node to free
 102  */
 103 static void node_free(struct node *node)
 104 {
 105         struct node *left, *right;
 106
 107         if (node) {
 108                 switch (node->type) {
 109                 case Text:
 110                         free(node);
 111                         break;
 112                 case And:
 113                 case Or:
 114                         left = node->children[0];
 115                         right = node->children[1];
 116                         free(node);
 117                         node_free(left);
 118                         node_free(right);
 119                         break;
 120                 case Not:
 121                         left = node->children[0];
 122                         free(node);
 123                         node_free(left);
 124                         break;
 125                 }
 126         }
 127 }
 128
 129 /**
 130  * Checks the permissions for the 'node' using the 'check' function
 131  * and its 'closure'.
 132  * @param node the node to check
 133  * @param check the function that checks if a pernmission of 'name' is granted for 'closure'
 134  * @param closure the context closure for the function 'check'
 135  * @return 1 if the permission is granted or 0 otherwise
 136  */
 137 static int node_check(struct node *node, int (*check)(void *closure, const char *name), void *closure)
 138 {
 139         int rc;
 140
 141         switch (node->type) {
 142         case Text:
 143                 rc = check(closure, node->text);
 144                 break;
 145         case And:
 146                 rc = node_check(node->children[0], check, closure);
 147                 if (rc)
 148                         rc = node_check(node->children[1], check, closure);
 149                 break;
 150         case Or:
 151                 rc = node_check(node->children[0], check, closure);
 152                 if (!rc)
 153                         rc = node_check(node->children[1], check, closure);
 154                 break;
 155         case Not:
 156                 rc = !node_check(node->children[0], check, closure);
 157                 break;
 158         }
 159         return rc;
 160 }
 161
 162 /*********************************************************************
 163 *** SECTION parse
 164 *********************************************************************/
 165
 166 /**
 167  * the symbol types
 168  */
 169 enum symbol
 170 {
 171         TEXT,   /**< a common text, name of a permission */
 172         AND,    /**< and keyword */
 173         OR,     /**< or keyword */
 174         NOT,    /**< not keyword */
 175         OBRA,   /**< open bracket */
 176         CBRA,   /**< close bracket */
 177         END     /**< end of input */
 178 };
 179
 180 /**
 181  * structure for parsing permission description
 182  */
 183 struct parse
 184 {
 185         const char *desc;       /**< initial permission description */
 186         const char *symbol;     /**< current symbol parsed */
 187         size_t symlen;          /**< length of the current symbol */
 188         enum symbol type;       /**< type of the current symbol */
 189 };
 190
 191 /**
 192  * updates parse to point to the next symbol if any
 193  * @param parse parser state to update
 194  */
 195 static void parse_next(struct parse *parse)
 196 {
 197         const char *scan;
 198         size_t len;
 199
 200         /* skip current symbol */
 201         scan = &parse->symbol[parse->symlen];
 202
 203         /* skip white spaces */
 204         while (*scan && isspace(*scan))
 205                 scan++;
 206
 207         /* scan the symbol */
 208         switch (*scan) {
 209         case 0:
 210                 len = 0;
 211                 parse->type = END;
 212                 break;
 213         case '(':
 214                 len = 1;
 215                 parse->type = OBRA;
 216                 break;
 217         case ')':
 218                 len = 1;
 219                 parse->type = CBRA;
 220                 break;
 221         default:
 222                 /* compute the length */
 223                 len = 0;
 224                 while (scan[len] && !isspace(scan[len]) && scan[len] != ')' && scan[len] != '(')
 225                         len++;
 226                 parse->type = TEXT;
 227
 228                 /* fall to keyword if any */
 229                 switch(len) {
 230                 case 2:
 231                         if (!strncasecmp(scan, "or", len))
 232                                 parse->type = OR;
 233                         break;
 234                 case 3:
 235                         if (!strncasecmp(scan, "and", len))
 236                                 parse->type = AND;
 237                         else if (!strncasecmp(scan, "not", len))
 238                                 parse->type = NOT;
 239                         break;
 240                 }
 241                 break;
 242         }
 243         parse->symbol = scan;
 244         parse->symlen = len;
 245 }
 246
 247 /**
 248  * Init the parser state 'parse' for the description 'desc'
 249  * @param parse the parser state to initialise
 250  * @param desc the description of the permissions to be parsed
 251  */
 252 static void parse_init(struct parse *parse, const char *desc)
 253 {
 254         parse->desc = desc;
 255         parse->symbol = desc;
 256         parse->symlen = 0;
 257         parse_next(parse);
 258 }
 259
 260 /*********************************************************************
 261 *** SECTION node_parse
 262 *********************************************************************/
 263
 264 static struct node *node_parse_or(struct parse *parse);
 265
 266 /**
 267  * Parse a permission name
 268  * @param parser the parser state
 269  * @return the parsed node or NULL in case of error
 270  * in case of error errno is set to EINVAL or ENOMEM
 271  */
 272 static struct node *node_parse_text(struct parse *parse)
 273 {
 274         struct node *node;
 275
 276         if (parse->type == TEXT) {
 277                 node = node_make_text(Text, parse->symbol, parse->symlen);
 278                 parse_next(parse);
 279         } else {
 280                 errno = EINVAL;
 281                 node = NULL;
 282         }
 283         return node;
 284 }
 285
 286 /**
 287  * Parse a term that is either a name (text) or a sub expression
 288  * enclosed in brackets.
 289  * @param parser the parser state
 290  * @return the parsed node or NULL in case of error
 291  * in case of error errno is set to EINVAL or ENOMEM
 292  */
 293 static struct node *node_parse_term(struct parse *parse)
 294 {
 295         struct node *node;
 296
 297         if (parse->type != OBRA)
 298                 node = node_parse_text(parse);
 299         else {
 300                 parse_next(parse);
 301                 node = node_parse_or(parse);
 302                 if (parse->type == CBRA)
 303                         parse_next(parse);
 304                 else {
 305                         errno = EINVAL;
 306                         node_free(node);
 307                         node = NULL;
 308                 }
 309         }
 310         return node;
 311 }
 312
 313 /**
 314  * Parse a term potentially prefixed by not.
 315  * @param parser the parser state
 316  * @return the parsed node or NULL in case of error
 317  * in case of error errno is set to EINVAL or ENOMEM
 318  */
 319 static struct node *node_parse_not(struct parse *parse)
 320 {
 321         struct node *node, *not;
 322
 323         if (parse->type != NOT)
 324                 node = node_parse_term(parse);
 325         else {
 326                 parse_next(parse);
 327                 node = node_parse_term(parse);
 328                 if (node) {
 329                         not = node_make_parent(Not, node, NULL);
 330                         if (not)
 331                                 node = not;
 332                         else {
 333                                 node_free(node);
 334                                 node = NULL;
 335                         }
 336                 }
 337         }
 338         return node;
 339 }
 340
 341 /**
 342  * Parse a potential sequence of terms connected with the
 343  * given operator (AND or OR). The function takes care to
 344  * create an evaluation tree that respects the order given
 345  * by the description and that will limit the recursivity
 346  * depth.
 347  * @param parser the parser state
 348  * @param operator the symbol type of the operator scanned
 349  * @param subparse the function for parsing terms of the sequence
 350  * @param type the node type corresponding to the operator
 351  * @return the parsed node or NULL in case of error
 352  * in case of error errno is set to EINVAL or ENOMEM
 353  */
 354 static struct node *node_parse_infix(
 355                 struct parse *parse,
 356                 enum symbol operator,
 357                 struct node *(*subparse)(struct parse*),
 358                 enum type type
 359 )
 360 {
 361         struct node *root, **up, *right, *node;
 362
 363         root = subparse(parse);
 364         if (root) {
 365                 up = &root;
 366                 while (parse->type == operator) {
 367                         parse_next(parse);
 368                         right = subparse(parse);
 369                         if (!right) {
 370                                 node_free(root);
 371                                 root = NULL;
 372                                 break;
 373                         }
 374                         node = node_make_parent(type, *up, right);
 375                         if (!node) {
 376                                 node_free(right);
 377                                 node_free(root);
 378                                 root = NULL;
 379                                 break;
 380                         }
 381                         *up = node;
 382                         up = &node->children[1];
 383                 }
 384         }
 385         return root;
 386 }
 387
 388 /**
 389  * Parse a potential sequence of anded terms.
 390  * @param parser the parser state
 391  * @return the parsed node or NULL in case of error
 392  * in case of error errno is set to EINVAL or ENOMEM
 393  */
 394 static struct node *node_parse_and(struct parse *parse)
 395 {
 396         return node_parse_infix(parse, AND, node_parse_not, And);
 397 }
 398
 399 /**
 400  * Parse a potential sequence of ored terms.
 401  * @param parser the parser state
 402  * @return the parsed node or NULL in case of error
 403  * in case of error errno is set to EINVAL or ENOMEM
 404  */
 405 static struct node *node_parse_or(struct parse *parse)
 406 {
 407         return node_parse_infix(parse, OR, node_parse_and, Or);
 408 }
 409
 410 /**
 411  * Parse description of permissions.
 412  * @param desc the description to parse
 413  * @return the parsed node or NULL in case of error
 414  * in case of error errno is set to EINVAL or ENOMEM
 415  */
 416 static struct node *node_parse(const char *desc)
 417 {
 418         struct node *node;
 419         struct parse parse;
 420
 421         parse_init(&parse, desc);
 422         node = node_parse_or(&parse);
 423         if (node && parse.type != END) {
 424                 node_free(node);
 425                 node = NULL;
 426         }
 427         return node;
 428 }
 429
 430 /*********************************************************************
 431 *** SECTION perm
 432 *********************************************************************/
 433
 434 /**
 435  * structure for storing permissions
 436  */
 437 struct afb_perm
 438 {
 439         struct node *root;      /**< root node descripbing the permission */
 440         int refcount;           /**< the count of use of the structure */
 441 };
 442
 443 /**
 444  * allocates the structure for the given root
 445  * @param root the root node to keep
 446  * @return the created permission object or NULL
 447  */
 448 static struct afb_perm *make_perm(struct node *root)
 449 {
 450         struct afb_perm *perm;
 451
 452         perm = malloc(sizeof *perm);
 453         if (!perm)
 454                 errno = ENOMEM;
 455         else {
 456                 perm->root = root;
 457                 perm->refcount = 1;
 458         }
 459         return perm;
 460 }
 461
 462 /**
 463  * Creates the permission for the given description
 464  * @param desc the description of the permission to create
 465  * @return the created permission object or NULL
 466  */
 467 struct afb_perm *afb_perm_parse(const char *desc)
 468 {
 469         struct node *root;
 470         struct afb_perm *perm;
 471
 472         root = node_parse(desc);
 473         if (root) {
 474                 perm = make_perm(root);
 475                 if (perm)
 476                         return perm;
 477                 node_free(root);
 478         }
 479         return NULL;
 480 }
 481
 482 /**
 483  * Adds a reference to the permissions
 484  * @param perm the permission to reference
 485  */
 486 void afb_perm_addref(struct afb_perm *perm)
 487 {
 488         assert(perm);
 489         perm->refcount++;
 490 }
 491
 492 /**
 493  * Removes a reference to the permissions
 494  * @param perm the permission to dereference
 495  */
 496 void afb_perm_unref(struct afb_perm *perm)
 497 {
 498         if (perm && !--perm->refcount) {
 499                 node_free(perm->root);
 500                 free(perm);
 501         }
 502 }
 503
 504 /**
 505  * Checks permission 'perm' using the 'check' function
 506  * and its 'closure'.
 507  * @param perm the permission to check
 508  * @param check the function that checks if a pernmission of 'name' is granted for 'closure'
 509  * @param closure the context closure for the function 'check'
 510  * @return 1 if the permission is granted or 0 otherwise
 511  */
 512 int afb_perm_check(struct afb_perm *perm, int (*check)(void *closure, const char *name), void *closure)
 513 {
 514         return node_check(perm->root, check, closure);
 515 }
 516
 517