1 /* authz.c : path-based access control
2 *
3 * ====================================================================
4 * Licensed to the Apache Software Foundation (ASF) under one
5 * or more contributor license agreements. See the NOTICE file
6 * distributed with this work for additional information
7 * regarding copyright ownership. The ASF licenses this file
8 * to you under the Apache License, Version 2.0 (the
9 * "License"); you may not use this file except in compliance
10 * with the License. You may obtain a copy of the License at
11 *
12 * http://www.apache.org/licenses/LICENSE-2.0
13 *
14 * Unless required by applicable law or agreed to in writing,
15 * software distributed under the License is distributed on an
16 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
17 * KIND, either express or implied. See the License for the
18 * specific language governing permissions and limitations
19 * under the License.
20 * ====================================================================
21 */
22
23
24 /*** Includes. ***/
25
26 #include <apr_pools.h>
27 #include <apr_file_io.h>
28 #include <apr_fnmatch.h>
29
30 #include "svn_hash.h"
31 #include "svn_pools.h"
32 #include "svn_error.h"
33 #include "svn_dirent_uri.h"
34 #include "svn_path.h"
35 #include "svn_repos.h"
36 #include "svn_config.h"
37 #include "svn_ctype.h"
38 #include "private/svn_atomic.h"
39 #include "private/svn_fspath.h"
40 #include "private/svn_repos_private.h"
41 #include "private/svn_sorts_private.h"
42 #include "private/svn_subr_private.h"
43 #include "repos.h"
44 #include "authz.h"
45 #include "config_file.h"
46
47
48 /*** Access rights. ***/
49
50 /* This structure describes the access rights given to a specific user by
51 * a path rule (actually the rule set specified for a path). I.e. there is
52 * one instance of this per path rule.
53 */
54 typedef struct path_access_t
55 {
56 /* Sequence number of the path rule that this struct was derived from.
57 * If multiple rules apply to the same path (only possible with wildcard
58 * matching), the one with the highest SEQUENCE_NUMBER wins, i.e. the latest
59 * one defined in the authz file.
60 *
61 * A value of 0 denotes the default rule at the repository root denying
62 * access to everybody. User-defined path rules start with ID 1.
63 */
64 int sequence_number;
65
66 /* Access rights of the respective user as defined by the rule set. */
67 authz_access_t rights;
68 } path_access_t;
69
70 /* Use this to indicate that no sequence ID has been assigned.
71 * It will automatically be inferior to (less than) any other sequence ID. */
72 #define NO_SEQUENCE_NUMBER (-1)
73
74 /* Convenience structure combining the node-local access rights with the
75 * min and max rights granted within the sub-tree. */
76 typedef struct limited_rights_t
77 {
78 /* Access granted to the current user. If the SEQUENCE_NUMBER member is
79 * NO_SEQUENCE_NUMBER, there has been no specific path rule for this PATH
80 * but only for some sub-path(s). There is always a rule at the root node.
81 */
82 path_access_t access;
83
84 /* Minimal access rights that the user has on this or any other node in
85 * the sub-tree. This does not take inherited rights into account. */
86 authz_access_t min_rights;
87
88 /* Maximal access rights that the user has on this or any other node in
89 * the sub-tree. This does not take inherited rights into account. */
90 authz_access_t max_rights;
91
92 } limited_rights_t;
93
94 /* Return TRUE, if RIGHTS has local rights defined in the ACCESS member. */
95 static svn_boolean_t
has_local_rule(const limited_rights_t * rights)96 has_local_rule(const limited_rights_t *rights)
97 {
98 return rights->access.sequence_number != NO_SEQUENCE_NUMBER;
99 }
100
101 /* Aggregate the ACCESS spec of TARGET and RIGHTS into TARGET. I.e. if both
102 * are specified, pick one in accordance to the precedence rules. */
103 static void
combine_access(limited_rights_t * target,const limited_rights_t * rights)104 combine_access(limited_rights_t *target,
105 const limited_rights_t *rights)
106 {
107 /* This implies the check for NO_SEQUENCE_NUMBER, i.e no rights being
108 * specified. */
109 if (target->access.sequence_number < rights->access.sequence_number)
110 target->access = rights->access;
111 }
112
113 /* Aggregate the min / max access rights of TARGET and RIGHTS into TARGET. */
114 static void
combine_right_limits(limited_rights_t * target,const limited_rights_t * rights)115 combine_right_limits(limited_rights_t *target,
116 const limited_rights_t *rights)
117 {
118 target->max_rights |= rights->max_rights;
119 target->min_rights &= rights->min_rights;
120 }
121
122
123
124 /*** Authz cache access. ***/
125
126 /* All authz instances currently in use as well as all filtered authz
127 * instances in use will be cached here.
128 * Both caches will be instantiated at most once. */
129 static svn_object_pool__t *authz_pool = NULL;
130 static svn_object_pool__t *filtered_pool = NULL;
131 static svn_atomic_t authz_pool_initialized = FALSE;
132
133 /* Implements svn_atomic__err_init_func_t. */
134 static svn_error_t *
synchronized_authz_initialize(void * baton,apr_pool_t * pool)135 synchronized_authz_initialize(void *baton, apr_pool_t *pool)
136 {
137 #if APR_HAS_THREADS
138 svn_boolean_t multi_threaded = TRUE;
139 #else
140 svn_boolean_t multi_threaded = FALSE;
141 #endif
142
143 SVN_ERR(svn_object_pool__create(&authz_pool, multi_threaded, pool));
144 SVN_ERR(svn_object_pool__create(&filtered_pool, multi_threaded, pool));
145
146 return SVN_NO_ERROR;
147 }
148
149 svn_error_t *
svn_repos_authz_initialize(apr_pool_t * pool)150 svn_repos_authz_initialize(apr_pool_t *pool)
151 {
152 /* Protect against multiple calls. */
153 return svn_error_trace(svn_atomic__init_once(&authz_pool_initialized,
154 synchronized_authz_initialize,
155 NULL, pool));
156 }
157
158 /* Return a combination of AUTHZ_KEY and GROUPS_KEY, allocated in RESULT_POOL.
159 * GROUPS_KEY may be NULL. This is the key for the AUTHZ_POOL.
160 */
161 static svn_membuf_t *
construct_authz_key(const svn_checksum_t * authz_key,const svn_checksum_t * groups_key,apr_pool_t * result_pool)162 construct_authz_key(const svn_checksum_t *authz_key,
163 const svn_checksum_t *groups_key,
164 apr_pool_t *result_pool)
165 {
166 svn_membuf_t *result = apr_pcalloc(result_pool, sizeof(*result));
167 if (groups_key)
168 {
169 apr_size_t authz_size = svn_checksum_size(authz_key);
170 apr_size_t groups_size = svn_checksum_size(groups_key);
171
172 svn_membuf__create(result, authz_size + groups_size, result_pool);
173 result->size = authz_size + groups_size; /* exact length is required! */
174
175 memcpy(result->data, authz_key->digest, authz_size);
176 memcpy((char *)result->data + authz_size,
177 groups_key->digest, groups_size);
178 }
179 else
180 {
181 apr_size_t size = svn_checksum_size(authz_key);
182 svn_membuf__create(result, size, result_pool);
183 result->size = size; /* exact length is required! */
184 memcpy(result->data, authz_key->digest, size);
185 }
186
187 return result;
188 }
189
190 /* Return a combination of REPOS_NAME, USER and AUTHZ_ID, allocated in
191 * RESULT_POOL. USER may be NULL. This is the key for the FILTERED_POOL.
192 */
193 static svn_membuf_t *
construct_filtered_key(const char * repos_name,const char * user,const svn_membuf_t * authz_id,apr_pool_t * result_pool)194 construct_filtered_key(const char *repos_name,
195 const char *user,
196 const svn_membuf_t *authz_id,
197 apr_pool_t *result_pool)
198 {
199 svn_membuf_t *result = apr_pcalloc(result_pool, sizeof(*result));
200 size_t repos_len = strlen(repos_name);
201 size_t user_len = user ? strlen(user) : 1;
202 const char *nullable_user = user ? user : "\0";
203 size_t size = authz_id->size + repos_len + 1 + user_len + 1;
204
205 svn_membuf__create(result, size, result_pool);
206 result->size = size;
207
208 memcpy(result->data, repos_name, repos_len + 1);
209 size = repos_len + 1;
210 memcpy((char *)result->data + size, nullable_user, user_len + 1);
211 size += user_len + 1;
212 memcpy((char *)result->data + size, authz_id->data, authz_id->size);
213
214 return result;
215 }
216
217
218 /*** Constructing the prefix tree. ***/
219
220 /* Since prefix arrays may have more than one hit, we need to link them
221 * for fast lookup. */
222 typedef struct sorted_pattern_t
223 {
224 /* The filtered tree node carrying the prefix. */
225 struct node_t *node;
226
227 /* Entry that is a prefix to this one or NULL. */
228 struct sorted_pattern_t *next;
229 } sorted_pattern_t;
230
231 /* Substructure of node_t. It contains all sub-node that use patterns
232 * in the next segment level. We keep it separate to save a bit of memory
233 * and to be able to check for pattern presence in a single operation.
234 */
235 typedef struct node_pattern_t
236 {
237 /* If not NULL, this represents the "*" follow-segment. */
238 struct node_t *any;
239
240 /* If not NULL, this represents the "**" follow-segment. */
241 struct node_t *any_var;
242
243 /* If not NULL, the segments of all sorted_pattern_t in this array are the
244 * prefix part of "prefix*" patterns. Sorted by segment prefix. */
245 apr_array_header_t *prefixes;
246
247 /* If not NULL, the segments of all sorted_pattern_t in this array are the
248 * reversed suffix part of "*suffix" patterns. Sorted by reversed
249 * segment suffix. */
250 apr_array_header_t *suffixes;
251
252 /* If not NULL, the segments of all sorted_pattern_t in this array contain
253 * wildcards and don't fit into any of the above categories.
254 * The NEXT members of the elements will not be used. */
255 apr_array_header_t *complex;
256
257 /* This node itself is a "**" segment and must therefore itself be added
258 * to the matching node list for the next level. */
259 svn_boolean_t repeat;
260 } node_pattern_t;
261
262 /* The pattern tree. All relevant path rules are being folded into this
263 * prefix tree, with a single, whole segment stored at each node. The whole
264 * tree applies to a single user only.
265 */
266 typedef struct node_t
267 {
268 /* The segment as specified in the path rule. During the lookup tree walk,
269 * this will compared to the respective segment of the path to check. */
270 svn_string_t segment;
271
272 /* Immediate access rights granted by rules on this node and the min /
273 * max rights on any path in this sub-tree. */
274 limited_rights_t rights;
275
276 /* Map of sub-segment(const char *) to respective node (node_t) for all
277 * sub-segments that have rules on themselves or their respective subtrees.
278 * NULL, if there are no rules for sub-paths relevant to the user. */
279 apr_hash_t *sub_nodes;
280
281 /* If not NULL, this contains the pattern-based segment sub-nodes. */
282 node_pattern_t *pattern_sub_nodes;
283 } node_t;
284
285 /* Create a new tree node for SEGMENT.
286 Note: SEGMENT->pattern is always interned and therefore does not
287 have to be copied into the result pool. */
288 static node_t *
create_node(authz_rule_segment_t * segment,apr_pool_t * result_pool)289 create_node(authz_rule_segment_t *segment,
290 apr_pool_t *result_pool)
291 {
292 node_t *result = apr_pcalloc(result_pool, sizeof(*result));
293 if (segment)
294 result->segment = segment->pattern;
295 else
296 {
297 result->segment.data = "";
298 result->segment.len = 0;
299 }
300 result->rights.access.sequence_number = NO_SEQUENCE_NUMBER;
301 return result;
302 }
303
304 /* Auto-create a node in *NODE, make it apply to SEGMENT and return it. */
305 static node_t *
ensure_node(node_t ** node,authz_rule_segment_t * segment,apr_pool_t * result_pool)306 ensure_node(node_t **node,
307 authz_rule_segment_t *segment,
308 apr_pool_t *result_pool)
309 {
310 if (!*node)
311 *node = create_node(segment, result_pool);
312
313 return *node;
314 }
315
316 /* compare_func comparing segment names. It takes a sorted_pattern_t* as
317 * VOID_LHS and a const authz_rule_segment_t * as VOID_RHS.
318 */
319 static int
compare_node_rule_segment(const void * void_lhs,const void * void_rhs)320 compare_node_rule_segment(const void *void_lhs,
321 const void *void_rhs)
322 {
323 const sorted_pattern_t *element = void_lhs;
324 const authz_rule_segment_t *segment = void_rhs;
325
326 return strcmp(element->node->segment.data, segment->pattern.data);
327 }
328
329 /* compare_func comparing segment names. It takes a sorted_pattern_t* as
330 * VOID_LHS and a const char * as VOID_RHS.
331 */
332 static int
compare_node_path_segment(const void * void_lhs,const void * void_rhs)333 compare_node_path_segment(const void *void_lhs,
334 const void *void_rhs)
335 {
336 const sorted_pattern_t *element = void_lhs;
337 const char *segment = void_rhs;
338
339 return strcmp(element->node->segment.data, segment);
340 }
341
342 /* Make sure a node_t* for SEGMENT exists in *ARRAY and return it.
343 * Auto-create either if they don't exist. Entries in *ARRAY are
344 * sorted by their segment strings.
345 */
346 static node_t *
ensure_node_in_array(apr_array_header_t ** array,authz_rule_segment_t * segment,apr_pool_t * result_pool)347 ensure_node_in_array(apr_array_header_t **array,
348 authz_rule_segment_t *segment,
349 apr_pool_t *result_pool)
350 {
351 int idx;
352 sorted_pattern_t entry;
353 sorted_pattern_t *entry_ptr;
354
355 /* Auto-create the array. */
356 if (!*array)
357 *array = apr_array_make(result_pool, 4, sizeof(sorted_pattern_t));
358
359 /* Find the node in ARRAY and the IDX at which it were to be inserted.
360 * Initialize IDX such that we won't attempt a hinted lookup (likely
361 * to fail and therefore pure overhead). */
362 idx = (*array)->nelts;
363 entry_ptr = svn_sort__array_lookup(*array, segment, &idx,
364 compare_node_rule_segment);
365 if (entry_ptr)
366 return entry_ptr->node;
367
368 /* There is no such node, yet.
369 * Create one and insert it into the sorted array. */
370 entry.node = create_node(segment, result_pool);
371 entry.next = NULL;
372 svn_error_clear(svn_sort__array_insert2(*array, &entry, idx));
373
374 return entry.node;
375 }
376
377 /* Auto-create the PATTERN_SUB_NODES sub-structure in *NODE and return it. */
378 static node_pattern_t *
ensure_pattern_sub_nodes(node_t * node,apr_pool_t * result_pool)379 ensure_pattern_sub_nodes(node_t *node,
380 apr_pool_t *result_pool)
381 {
382 if (node->pattern_sub_nodes == NULL)
383 node->pattern_sub_nodes = apr_pcalloc(result_pool,
384 sizeof(*node->pattern_sub_nodes));
385
386 return node->pattern_sub_nodes;
387 }
388
389 /* Combine an ACL rule segment with the corresponding node in our filtered
390 * data model. */
391 typedef struct node_segment_pair_t
392 {
393 authz_rule_segment_t *segment;
394 node_t *node;
395 } node_segment_pair_t;
396
397 /* Context object to be used with process_acl. It allows us to re-use
398 * information from previous insertions. */
399 typedef struct construction_context_t
400 {
401 /* Array of node_segment_pair_t. It contains all segments already
402 * processed of the current insertion together with the respective
403 * nodes in our filtered tree. Before the next lookup, the tree
404 * walk for the common prefix can be skipped. */
405 apr_array_header_t *path;
406 } construction_context_t;
407
408 /* Return a new context object allocated in RESULT_POOL. */
409 static construction_context_t *
create_construction_context(apr_pool_t * result_pool)410 create_construction_context(apr_pool_t *result_pool)
411 {
412 construction_context_t *result = apr_pcalloc(result_pool, sizeof(*result));
413
414 /* Array will be auto-extended but this initial size will make it rarely
415 * ever necessary. */
416 result->path = apr_array_make(result_pool, 32, sizeof(node_segment_pair_t));
417
418 return result;
419 }
420
421 /* Constructor utility: Below NODE, recursively insert sub-nodes for the
422 * path given as *SEGMENTS of length SEGMENT_COUNT. If matching nodes
423 * already exist, use those instead of creating new ones. Set the leave
424 * node's access rights spec to PATH_ACCESS. Update the context info in CTX.
425 */
426 static void
insert_path(construction_context_t * ctx,node_t * node,path_access_t * path_access,int segment_count,authz_rule_segment_t * segment,apr_pool_t * result_pool,apr_pool_t * scratch_pool)427 insert_path(construction_context_t *ctx,
428 node_t *node,
429 path_access_t *path_access,
430 int segment_count,
431 authz_rule_segment_t *segment,
432 apr_pool_t *result_pool,
433 apr_pool_t *scratch_pool)
434 {
435 node_t *sub_node;
436 node_segment_pair_t *node_segment;
437
438 /* End of path? */
439 if (segment_count == 0)
440 {
441 /* Set access rights. Note that there might be multiple rules for
442 * the same path due to non-repo-specific rules vs. repo-specific
443 * ones. Whichever gets defined last wins.
444 */
445 limited_rights_t rights;
446 rights.access = *path_access;
447 rights.max_rights = path_access->rights;
448 rights.min_rights = path_access->rights;
449 combine_access(&node->rights, &rights);
450 return;
451 }
452
453 /* Any wildcards? They will go into a separate sub-structure. */
454 if (segment->kind != authz_rule_literal)
455 ensure_pattern_sub_nodes(node, result_pool);
456
457 switch (segment->kind)
458 {
459 /* A full wildcard segment? */
460 case authz_rule_any_segment:
461 sub_node = ensure_node(&node->pattern_sub_nodes->any,
462 segment, result_pool);
463 break;
464
465 /* One or more full wildcard segments? */
466 case authz_rule_any_recursive:
467 sub_node = ensure_node(&node->pattern_sub_nodes->any_var,
468 segment, result_pool);
469 ensure_pattern_sub_nodes(sub_node, result_pool)->repeat = TRUE;
470 break;
471
472 /* A single wildcard at the end of the segment? */
473 case authz_rule_prefix:
474 sub_node = ensure_node_in_array(&node->pattern_sub_nodes->prefixes,
475 segment, result_pool);
476 break;
477
478 /* A single wildcard at the start of segments? */
479 case authz_rule_suffix:
480 sub_node = ensure_node_in_array(&node->pattern_sub_nodes->suffixes,
481 segment, result_pool);
482 break;
483
484 /* General pattern? */
485 case authz_rule_fnmatch:
486 sub_node = ensure_node_in_array(&node->pattern_sub_nodes->complex,
487 segment, result_pool);
488 break;
489
490 /* Then it must be a literal. */
491 default:
492 SVN_ERR_ASSERT_NO_RETURN(segment->kind == authz_rule_literal);
493
494 if (!node->sub_nodes)
495 {
496 node->sub_nodes = svn_hash__make(result_pool);
497 sub_node = NULL;
498 }
499 else
500 {
501 sub_node = svn_hash_gets(node->sub_nodes, segment->pattern.data);
502 }
503
504 /* Auto-insert a sub-node for the current segment. */
505 if (!sub_node)
506 {
507 sub_node = create_node(segment, result_pool);
508 apr_hash_set(node->sub_nodes,
509 sub_node->segment.data,
510 sub_node->segment.len,
511 sub_node);
512 }
513 }
514
515 /* Update context. */
516 node_segment = apr_array_push(ctx->path);
517 node_segment->segment = segment;
518 node_segment->node = sub_node;
519
520 /* Continue at the sub-node with the next segment. */
521 insert_path(ctx, sub_node, path_access, segment_count - 1, segment + 1,
522 result_pool, scratch_pool);
523 }
524
525
526 /* If the ACL is relevant to the REPOSITORY and user (given as MEMBERSHIPS
527 * plus ANONYMOUS flag), insert the respective nodes into tree starting
528 * at ROOT. Use the context info of the previous call in CTX to eliminate
529 * repeated lookups. Allocate new nodes in RESULT_POOL and use SCRATCH_POOL
530 * for temporary allocations.
531 */
532 static void
process_acl(construction_context_t * ctx,const authz_acl_t * acl,node_t * root,const char * repository,const char * user,apr_pool_t * result_pool,apr_pool_t * scratch_pool)533 process_acl(construction_context_t *ctx,
534 const authz_acl_t *acl,
535 node_t *root,
536 const char *repository,
537 const char *user,
538 apr_pool_t *result_pool,
539 apr_pool_t *scratch_pool)
540 {
541 path_access_t path_access;
542 int i;
543 node_t *node;
544
545 /* Skip ACLs that don't say anything about the current user
546 and/or repository. */
547 if (!svn_authz__get_acl_access(&path_access.rights, acl, user, repository))
548 return;
549
550 /* Insert the rule into the filtered tree. */
551 path_access.sequence_number = acl->sequence_number;
552
553 /* Try to reuse results from previous runs.
554 * Basically, skip the common prefix. */
555 node = root;
556 for (i = 0; i < ctx->path->nelts; ++i)
557 {
558 const node_segment_pair_t *step
559 = &APR_ARRAY_IDX(ctx->path, i, const node_segment_pair_t);
560
561 /* Exploit the fact that all strings in the authz model are unique /
562 * internized and can be identified by address alone. */
563 if ( !step->node
564 || i >= acl->rule.len
565 || step->segment->kind != acl->rule.path[i].kind
566 || step->segment->pattern.data != acl->rule.path[i].pattern.data)
567 {
568 ctx->path->nelts = i;
569 break;
570 }
571 else
572 {
573 node = step->node;
574 }
575 }
576
577 /* Insert the path rule into the filtered tree. */
578 insert_path(ctx, node, &path_access,
579 acl->rule.len - i, acl->rule.path + i,
580 result_pool, scratch_pool);
581 }
582
583 /* Forward declaration ... */
584 static svn_boolean_t
585 trim_tree(node_t *node,
586 int latest_any_var,
587 apr_pool_t *scratch_pool);
588
589 /* Call trim_tree() with LATEST_ANY_VAR on all elements in the *HASH of
590 * node_t * and remove empty nodes from. *HASH may be NULL. If all nodes
591 * could be removed, set *HASH to NULL and return TRUE. Allocate temporary
592 * data in SCRATCH_POOL.
593 */
594 static svn_boolean_t
trim_subnode_hash(apr_hash_t ** hash,int latest_any_var,apr_pool_t * scratch_pool)595 trim_subnode_hash(apr_hash_t **hash,
596 int latest_any_var,
597 apr_pool_t *scratch_pool)
598 {
599 if (*hash)
600 {
601 apr_array_header_t *to_remove = apr_array_make(scratch_pool, 0,
602 sizeof(node_t *));
603
604 apr_hash_index_t *hi;
605 for (hi = apr_hash_first(scratch_pool, *hash);
606 hi;
607 hi = apr_hash_next(hi))
608 {
609 node_t *node = apr_hash_this_val(hi);
610 if (trim_tree(node, latest_any_var, scratch_pool))
611 APR_ARRAY_PUSH(to_remove, node_t *) = node;
612 }
613
614 /* Are some nodes left? */
615 if (to_remove->nelts < apr_hash_count(*hash))
616 {
617 /* Remove empty nodes (if any). */
618 int i;
619 for (i = 0; i < to_remove->nelts; ++i)
620 {
621 node_t *node = APR_ARRAY_IDX(to_remove, i, node_t *);
622 apr_hash_set(*hash, node->segment.data, node->segment.len,
623 NULL);
624 }
625
626 return FALSE;
627 }
628
629 /* No nodes left. A NULL hash is more efficient than an empty one. */
630 *hash = NULL;
631 }
632
633 return TRUE;
634 }
635
636 /* Call trim_tree() with LATEST_ANY_VAR on all elements in the *ARRAY of
637 * node_t * and remove empty nodes from. *ARRAY may be NULL. If all nodes
638 * could be removed, set *ARRAY to NULL and return TRUE. Allocate
639 * temporary data in SCRATCH_POOL.
640 */
641 static svn_boolean_t
trim_subnode_array(apr_array_header_t ** array,int latest_any_var,apr_pool_t * scratch_pool)642 trim_subnode_array(apr_array_header_t **array,
643 int latest_any_var,
644 apr_pool_t *scratch_pool)
645 {
646 if (*array)
647 {
648 int i, dest;
649 for (i = 0, dest = 0; i < (*array)->nelts; ++i)
650 {
651 node_t *node = APR_ARRAY_IDX(*array, i, sorted_pattern_t).node;
652 if (!trim_tree(node, latest_any_var, scratch_pool))
653 {
654 if (i != dest)
655 APR_ARRAY_IDX(*array, dest, sorted_pattern_t)
656 = APR_ARRAY_IDX(*array, i, sorted_pattern_t);
657 ++dest;
658 }
659 }
660
661 /* Are some nodes left? */
662 if (dest)
663 {
664 /* Trim it to the number of valid entries. */
665 (*array)->nelts = dest;
666 return FALSE;
667 }
668
669 /* No nodes left. A NULL array is more efficient than an empty one. */
670 *array = NULL;
671 }
672
673 return TRUE;
674 }
675
676 /* Remove all rules and sub-nodes from NODE that are fully eclipsed by the
677 * "any-var" rule with sequence number LATEST_ANY_VAR. Return TRUE, if
678 * there are no rules left in the sub-tree, including NODE.
679 * Allocate temporary data in SCRATCH_POOL.
680 */
681 static svn_boolean_t
trim_tree(node_t * node,int latest_any_var,apr_pool_t * scratch_pool)682 trim_tree(node_t *node,
683 int latest_any_var,
684 apr_pool_t *scratch_pool)
685 {
686 svn_boolean_t removed_all = TRUE;
687
688 /* For convenience, we allow NODE to be NULL: */
689 if (!node)
690 return TRUE;
691
692 /* Do we have a later "any_var" rule at this node. */
693 if ( node->pattern_sub_nodes
694 && node->pattern_sub_nodes->any_var
695 && node->pattern_sub_nodes->any_var->rights.access.sequence_number
696 > latest_any_var)
697 {
698 latest_any_var
699 = node->pattern_sub_nodes->any_var->rights.access.sequence_number;
700 }
701
702 /* Is there a local rule at this node that is not eclipsed by any_var? */
703 if (has_local_rule(&node->rights))
704 {
705 /* Remove the local rule, if it got eclipsed.
706 * Note that for the latest any_var node, the sequence number is equal. */
707 if (node->rights.access.sequence_number >= latest_any_var)
708 removed_all = FALSE;
709 else
710 node->rights.access.sequence_number = NO_SEQUENCE_NUMBER;
711 }
712
713 /* Process all sub-nodes. */
714 removed_all &= trim_subnode_hash(&node->sub_nodes, latest_any_var,
715 scratch_pool);
716
717 if (node->pattern_sub_nodes)
718 {
719 if (trim_tree(node->pattern_sub_nodes->any, latest_any_var,
720 scratch_pool))
721 node->pattern_sub_nodes->any = NULL;
722 else
723 removed_all = FALSE;
724
725 if (trim_tree(node->pattern_sub_nodes->any_var, latest_any_var,
726 scratch_pool))
727 node->pattern_sub_nodes->any_var = NULL;
728 else
729 removed_all = FALSE;
730
731 removed_all &= trim_subnode_array(&node->pattern_sub_nodes->prefixes,
732 latest_any_var, scratch_pool);
733 removed_all &= trim_subnode_array(&node->pattern_sub_nodes->suffixes,
734 latest_any_var, scratch_pool);
735 removed_all &= trim_subnode_array(&node->pattern_sub_nodes->complex,
736 latest_any_var, scratch_pool);
737
738 /* Trim the tree as much as possible to speed up lookup(). */
739 if (removed_all)
740 node->pattern_sub_nodes = NULL;
741 }
742
743 return removed_all;
744 }
745
746 /* Forward declaration ... */
747 static void
748 finalize_tree(node_t *node,
749 limited_rights_t *sum,
750 apr_pool_t *scratch_pool);
751
752 /* Call finalize_tree() on all elements in the HASH of node_t *, passing
753 * SUM along. HASH may be NULL. Use SCRATCH_POOL for temporary allocations.
754 */
755 static void
finalize_subnode_hash(apr_hash_t * hash,limited_rights_t * sum,apr_pool_t * scratch_pool)756 finalize_subnode_hash(apr_hash_t *hash,
757 limited_rights_t *sum,
758 apr_pool_t *scratch_pool)
759 {
760 if (hash)
761 {
762 apr_hash_index_t *hi;
763 for (hi = apr_hash_first(scratch_pool, hash);
764 hi;
765 hi = apr_hash_next(hi))
766 finalize_tree(apr_hash_this_val(hi), sum, scratch_pool);
767 }
768 }
769
770 /* Call finalize_up_tree() on all elements in the ARRAY of node_t *,
771 * passing SUM along. ARRAY may be NULL. Use SCRATCH_POOL for temporary
772 * allocations.
773 */
774 static void
finalize_subnode_array(apr_array_header_t * array,limited_rights_t * sum,apr_pool_t * scratch_pool)775 finalize_subnode_array(apr_array_header_t *array,
776 limited_rights_t *sum,
777 apr_pool_t *scratch_pool)
778 {
779 if (array)
780 {
781 int i;
782 for (i = 0; i < array->nelts; ++i)
783 finalize_tree(APR_ARRAY_IDX(array, i, sorted_pattern_t).node, sum,
784 scratch_pool);
785 }
786 }
787
788 /* Link prefixes within the sorted ARRAY. */
789 static void
link_prefix_patterns(apr_array_header_t * array)790 link_prefix_patterns(apr_array_header_t *array)
791 {
792 int i;
793 if (!array)
794 return;
795
796 for (i = 1; i < array->nelts; ++i)
797 {
798 sorted_pattern_t *prev
799 = &APR_ARRAY_IDX(array, i - 1, sorted_pattern_t);
800 sorted_pattern_t *pattern
801 = &APR_ARRAY_IDX(array, i, sorted_pattern_t);
802
803 /* Does PATTERN potentially have a prefix in ARRAY?
804 * If so, at least the first char must match with the predecessor's
805 * because the array is sorted by that string. */
806 if (prev->node->segment.data[0] != pattern->node->segment.data[0])
807 continue;
808
809 /* Only the predecessor or any of its prefixes can be the closest
810 * prefix to PATTERN. */
811 for ( ; prev; prev = prev->next)
812 if ( prev->node->segment.len < pattern->node->segment.len
813 && !memcmp(prev->node->segment.data,
814 pattern->node->segment.data,
815 prev->node->segment.len))
816 {
817 pattern->next = prev;
818 break;
819 }
820 }
821 }
822
823 /* Recursively finalization the tree node properties for NODE. Update SUM
824 * (of NODE's parent) by combining it with the recursive access rights info
825 * on NODE. Use SCRATCH_POOL for temporary allocations.
826 */
827 static void
finalize_tree(node_t * node,limited_rights_t * sum,apr_pool_t * scratch_pool)828 finalize_tree(node_t *node,
829 limited_rights_t *sum,
830 apr_pool_t *scratch_pool)
831 {
832 limited_rights_t *local_sum = &node->rights;
833
834 /* For convenience, we allow NODE to be NULL: */
835 if (!node)
836 return;
837
838 /* Sum of rights at NODE - so far. */
839 if (has_local_rule(local_sum))
840 {
841 local_sum->max_rights = local_sum->access.rights;
842 local_sum->min_rights = local_sum->access.rights;
843 }
844 else
845 {
846 local_sum->min_rights = authz_access_write;
847 local_sum->max_rights = authz_access_none;
848 }
849
850 /* Process all sub-nodes. */
851 finalize_subnode_hash(node->sub_nodes, local_sum, scratch_pool);
852
853 if (node->pattern_sub_nodes)
854 {
855 finalize_tree(node->pattern_sub_nodes->any, local_sum, scratch_pool);
856 finalize_tree(node->pattern_sub_nodes->any_var, local_sum, scratch_pool);
857
858 finalize_subnode_array(node->pattern_sub_nodes->prefixes, local_sum,
859 scratch_pool);
860 finalize_subnode_array(node->pattern_sub_nodes->suffixes, local_sum,
861 scratch_pool);
862 finalize_subnode_array(node->pattern_sub_nodes->complex, local_sum,
863 scratch_pool);
864
865 /* Link up the prefixes / suffixes. */
866 link_prefix_patterns(node->pattern_sub_nodes->prefixes);
867 link_prefix_patterns(node->pattern_sub_nodes->suffixes);
868 }
869
870 /* Add our min / max info to the parent's info.
871 * Idempotent for parent == node (happens at root). */
872 combine_right_limits(sum, local_sum);
873 }
874
875 /* From the authz CONFIG, extract the parts relevant to USER and REPOSITORY.
876 * Return the filtered rule tree.
877 */
878 static node_t *
create_user_authz(authz_full_t * authz,const char * repository,const char * user,apr_pool_t * result_pool,apr_pool_t * scratch_pool)879 create_user_authz(authz_full_t *authz,
880 const char *repository,
881 const char *user,
882 apr_pool_t *result_pool,
883 apr_pool_t *scratch_pool)
884 {
885 int i;
886 node_t *root = create_node(NULL, result_pool);
887 construction_context_t *ctx = create_construction_context(scratch_pool);
888
889 /* Use a separate sub-pool to keep memory usage tight. */
890 apr_pool_t *subpool = svn_pool_create(scratch_pool);
891
892 /* Find all ACLs for REPOSITORY. */
893 apr_array_header_t *acls = apr_array_make(subpool, authz->acls->nelts,
894 sizeof(authz_acl_t *));
895 for (i = 0; i < authz->acls->nelts; ++i)
896 {
897 const authz_acl_t *acl = &APR_ARRAY_IDX(authz->acls, i, authz_acl_t);
898 if (svn_authz__acl_applies_to_repo(acl, repository))
899 {
900 /* ACLs in the AUTHZ are sorted by path and repository.
901 * So, if there is a rule for the repo and a global rule for the
902 * same path, we will detect them here. */
903 if (acls->nelts)
904 {
905 const authz_acl_t *prev_acl
906 = APR_ARRAY_IDX(acls, acls->nelts - 1, const authz_acl_t *);
907 if (svn_authz__compare_paths(&prev_acl->rule, &acl->rule) == 0)
908 {
909 svn_boolean_t global_acl_applies;
910 svn_boolean_t repos_acl_applies;
911
912 /* Previous ACL is a global rule. */
913 SVN_ERR_ASSERT_NO_RETURN(!strcmp(prev_acl->rule.repos,
914 AUTHZ_ANY_REPOSITORY));
915 /* Current ACL is a per-repository rule. */
916 SVN_ERR_ASSERT_NO_RETURN(strcmp(acl->rule.repos,
917 AUTHZ_ANY_REPOSITORY));
918
919 global_acl_applies =
920 svn_authz__get_acl_access(NULL, prev_acl, user, repository);
921 repos_acl_applies =
922 svn_authz__get_acl_access(NULL, acl, user, repository);
923
924 /* Prefer rules which apply to both this user and this path
925 * over rules which apply only to the path. In cases where
926 * both rules apply to user and path, always prefer the
927 * repository-specific rule. */
928 if (!global_acl_applies || repos_acl_applies)
929 {
930 apr_array_pop(acls);
931 APR_ARRAY_PUSH(acls, const authz_acl_t *) = acl;
932 }
933 }
934 else
935 APR_ARRAY_PUSH(acls, const authz_acl_t *) = acl;
936 }
937 else
938 APR_ARRAY_PUSH(acls, const authz_acl_t *) = acl;
939 }
940 }
941
942 /* Filtering and tree construction. */
943 for (i = 0; i < acls->nelts; ++i)
944 process_acl(ctx, APR_ARRAY_IDX(acls, i, const authz_acl_t *),
945 root, repository, user, result_pool, subpool);
946
947 /* If there is no relevant rule at the root node, the "no access" default
948 * applies. Give it a SEQUENCE_NUMBER that will never overrule others. */
949 if (!has_local_rule(&root->rights))
950 {
951 root->rights.access.sequence_number = 0;
952 root->rights.access.rights = authz_access_none;
953 }
954
955 /* Trim the tree.
956 *
957 * We can't do pattern comparison, so for most pattern rules we cannot
958 * say that a set of rules "eclipses" / overrides a given other set of
959 * rules for all possible paths. That limits the accuracy of our check
960 * for recursive access in similar ways than for non-pattern rules.
961 *
962 * However, the user expects a rule ending with "**" to eclipse any older
963 * rule in that sub-tree recursively. So, this trim function removes
964 * eclipsed nodes from the tree.
965 */
966 svn_pool_clear(subpool);
967 trim_tree(root, NO_SEQUENCE_NUMBER, subpool);
968
969 /* Calculate recursive rights.
970 *
971 * This is a bottom-up calculation of the range of access rights
972 * specified anywhere in the respective sub-tree, including the base
973 * node itself.
974 *
975 * To prevent additional finalization passes, we piggy-back the addition
976 * of the ordering links of the prefix and suffix sub-node rules.
977 */
978 svn_pool_clear(subpool);
979 finalize_tree(root, &root->rights, subpool);
980
981 /* Done. */
982 svn_pool_destroy(subpool);
983 return root;
984 }
985
986
987 /*** Lookup. ***/
988
989 /* Reusable lookup state object. It is easy to pass to functions and
990 * recycling it between lookups saves significant setup costs. */
991 typedef struct lookup_state_t
992 {
993 /* Rights immediately applying to this node and limits to the rights to
994 * any sub-path. */
995 limited_rights_t rights;
996
997 /* Nodes applying to the path followed so far. */
998 apr_array_header_t *current;
999
1000 /* Temporary array containing the nodes applying to the next path
1001 * segment (used to build up the next contents of CURRENT). */
1002 apr_array_header_t *next;
1003
1004 /* Scratch pad for path operations. */
1005 svn_stringbuf_t *scratch_pad;
1006
1007 /* After each lookup iteration, CURRENT and PARENT_RIGHTS will
1008 * apply to this path. */
1009 svn_stringbuf_t *parent_path;
1010
1011 /* Rights that apply at PARENT_PATH, if PARENT_PATH is not empty. */
1012 limited_rights_t parent_rights;
1013
1014 } lookup_state_t;
1015
1016 /* Constructor for lookup_state_t. */
1017 static lookup_state_t *
create_lookup_state(apr_pool_t * result_pool)1018 create_lookup_state(apr_pool_t *result_pool)
1019 {
1020 lookup_state_t *state = apr_pcalloc(result_pool, sizeof(*state));
1021
1022 state->next = apr_array_make(result_pool, 4, sizeof(node_t *));
1023 state->current = apr_array_make(result_pool, 4, sizeof(node_t *));
1024
1025 /* Virtually all path segments should fit into this buffer. If they
1026 * don't, the buffer gets automatically reallocated.
1027 *
1028 * Using a smaller initial size would be fine as well but does not
1029 * buy us much for the increased risk of being expanded anyway - at
1030 * some extra cost. */
1031 state->scratch_pad = svn_stringbuf_create_ensure(200, result_pool);
1032
1033 /* Most paths should fit into this buffer. The same rationale as
1034 * above applies. */
1035 state->parent_path = svn_stringbuf_create_ensure(200, result_pool);
1036
1037 return state;
1038 }
1039
1040 /* Clear the current contents of STATE and re-initialize it for ROOT.
1041 * Check whether we can reuse a previous parent path lookup to shorten
1042 * the current PATH walk. Return the full or remaining portion of
1043 * PATH, respectively. PATH must not be NULL. */
1044 static const char *
init_lockup_state(lookup_state_t * state,node_t * root,const char * path)1045 init_lockup_state(lookup_state_t *state,
1046 node_t *root,
1047 const char *path)
1048 {
1049 apr_size_t len = strlen(path);
1050 if ( (len > state->parent_path->len)
1051 && state->parent_path->len
1052 && (path[state->parent_path->len] == '/')
1053 && !memcmp(path, state->parent_path->data, state->parent_path->len))
1054 {
1055 /* The PARENT_PATH of the previous lookup is actually a parent path
1056 * of PATH. The CURRENT node list already matches the parent path
1057 * and we only have to set the correct rights info. */
1058 state->rights = state->parent_rights;
1059
1060 /* Tell the caller where to proceed. */
1061 return path + state->parent_path->len;
1062 }
1063
1064 /* Start lookup at ROOT for the full PATH. */
1065 state->rights = root->rights;
1066 state->parent_rights = root->rights;
1067
1068 apr_array_clear(state->next);
1069 apr_array_clear(state->current);
1070 APR_ARRAY_PUSH(state->current, node_t *) = root;
1071
1072 /* Var-segment rules match empty segments as well */
1073 if (root->pattern_sub_nodes && root->pattern_sub_nodes->any_var)
1074 {
1075 node_t *node = root->pattern_sub_nodes->any_var;
1076
1077 /* This is non-recursive due to ACL normalization. */
1078 combine_access(&state->rights, &node->rights);
1079 combine_right_limits(&state->rights, &node->rights);
1080 APR_ARRAY_PUSH(state->current, node_t *) = node;
1081 }
1082
1083 svn_stringbuf_setempty(state->parent_path);
1084 svn_stringbuf_setempty(state->scratch_pad);
1085
1086 return path;
1087 }
1088
1089 /* Add NODE to the list of NEXT nodes in STATE. NODE may be NULL in which
1090 * case this is a no-op. Also update and aggregate the access rights data
1091 * for the next path segment.
1092 */
1093 static void
add_next_node(lookup_state_t * state,node_t * node)1094 add_next_node(lookup_state_t *state,
1095 node_t *node)
1096 {
1097 /* Allowing NULL nodes simplifies the caller. */
1098 if (node)
1099 {
1100 /* The rule with the highest sequence number is the one that applies.
1101 * Not all nodes that we are following have rules that apply directly
1102 * to this path but are mere intermediates that may only have some
1103 * matching deep sub-node. */
1104 combine_access(&state->rights, &node->rights);
1105
1106 /* The rule tree node can be seen as an overlay of all the nodes that
1107 * we are following. Any of them _may_ match eventually, so the min/
1108 * max possible access rights are a combination of all these sub-trees.
1109 */
1110 combine_right_limits(&state->rights, &node->rights);
1111
1112 /* NODE is now enlisted as a (potential) match for the next segment. */
1113 APR_ARRAY_PUSH(state->next, node_t *) = node;
1114
1115 /* Variable length sub-segment sequences apply to the same node as
1116 * they match empty sequences as well. */
1117 if (node->pattern_sub_nodes && node->pattern_sub_nodes->any_var)
1118 {
1119 node = node->pattern_sub_nodes->any_var;
1120
1121 /* This is non-recursive due to ACL normalization. */
1122 combine_access(&state->rights, &node->rights);
1123 combine_right_limits(&state->rights, &node->rights);
1124 APR_ARRAY_PUSH(state->next, node_t *) = node;
1125 }
1126 }
1127 }
1128
1129 /* If PREFIX is indeed a prefix (or exact match) or SEGMENT, add the
1130 * node in PREFIX to STATE. */
1131 static void
add_if_prefix_matches(lookup_state_t * state,const sorted_pattern_t * prefix,const svn_stringbuf_t * segment)1132 add_if_prefix_matches(lookup_state_t *state,
1133 const sorted_pattern_t *prefix,
1134 const svn_stringbuf_t *segment)
1135 {
1136 node_t *node = prefix->node;
1137 if ( node->segment.len <= segment->len
1138 && !memcmp(node->segment.data, segment->data, node->segment.len))
1139 add_next_node(state, node);
1140 }
1141
1142 /* Scan the PREFIXES array of node_t* for all entries whose SEGMENT members
1143 * are prefixes of SEGMENT. Add these to STATE for the next tree level. */
1144 static void
add_prefix_matches(lookup_state_t * state,const svn_stringbuf_t * segment,apr_array_header_t * prefixes)1145 add_prefix_matches(lookup_state_t *state,
1146 const svn_stringbuf_t *segment,
1147 apr_array_header_t *prefixes)
1148 {
1149 /* Index of the first node that might be a match. All matches will
1150 * be at this and the immediately following indexes. */
1151 int i = svn_sort__bsearch_lower_bound(prefixes, segment->data,
1152 compare_node_path_segment);
1153
1154 /* The entry we found may be an exact match (but not a true prefix).
1155 * The prefix matching test will still work. */
1156 if (i < prefixes->nelts)
1157 add_if_prefix_matches(state,
1158 &APR_ARRAY_IDX(prefixes, i, sorted_pattern_t),
1159 segment);
1160
1161 /* The immediate predecessor may be a true prefix and all potential
1162 * prefixes can be found following the NEXT links between the array
1163 * indexes. */
1164 if (i > 0)
1165 {
1166 sorted_pattern_t *pattern;
1167 for (pattern = &APR_ARRAY_IDX(prefixes, i - 1, sorted_pattern_t);
1168 pattern;
1169 pattern = pattern->next)
1170 {
1171 add_if_prefix_matches(state, pattern, segment);
1172 }
1173 }
1174 }
1175
1176 /* Scan the PATTERNS array of node_t* for all entries whose SEGMENT members
1177 * (usually containing wildcards) match SEGMENT. Add these to STATE for the
1178 * next tree level. */
1179 static void
add_complex_matches(lookup_state_t * state,const svn_stringbuf_t * segment,apr_array_header_t * patterns)1180 add_complex_matches(lookup_state_t *state,
1181 const svn_stringbuf_t *segment,
1182 apr_array_header_t *patterns)
1183 {
1184 int i;
1185 for (i = 0; i < patterns->nelts; ++i)
1186 {
1187 node_t *node = APR_ARRAY_IDX(patterns, i, sorted_pattern_t).node;
1188 if (0 == apr_fnmatch(node->segment.data, segment->data, 0))
1189 add_next_node(state, node);
1190 }
1191 }
1192
1193 /* Extract the next segment from PATH and copy it into SEGMENT, whose current
1194 * contents get overwritten. Empty paths ("") are supported and leading '/'
1195 * segment separators will be interpreted as an empty segment (""). Non-
1196 * normalizes parts, i.e. sequences of '/', will be treated as a single '/'.
1197 *
1198 * Return the start of the next segment within PATH, skipping the '/'
1199 * separator(s). Return NULL, if there are no further segments.
1200 *
1201 * The caller (only called by lookup(), ATM) must ensure that SEGMENT has
1202 * enough room to store all of PATH.
1203 */
1204 static const char *
next_segment(svn_stringbuf_t * segment,const char * path)1205 next_segment(svn_stringbuf_t *segment,
1206 const char *path)
1207 {
1208 apr_size_t len;
1209 char c;
1210
1211 /* Read and scan PATH for NUL and '/' -- whichever comes first. */
1212 for (len = 0, c = *path; c; c = path[++len])
1213 if (c == '/')
1214 {
1215 /* End of segment. */
1216 segment->data[len] = 0;
1217 segment->len = len;
1218
1219 /* If PATH is not normalized, this is where we skip whole sequences
1220 * of separators. */
1221 while (path[++len] == '/')
1222 ;
1223
1224 /* Continue behind the last separator in the sequence. We will
1225 * treat trailing '/' as indicating an empty trailing segment.
1226 * Therefore, we never have to return NULL here. */
1227 return path + len;
1228 }
1229 else
1230 {
1231 /* Copy segment contents directly into the result buffer.
1232 * On many architectures, this is almost or entirely for free. */
1233 segment->data[len] = c;
1234 }
1235
1236 /* No separator found, so all of PATH has been the last segment. */
1237 segment->data[len] = 0;
1238 segment->len = len;
1239
1240 /* Tell the caller that this has been the last segment. */
1241 return NULL;
1242 }
1243
1244 /* Starting at the respective user's authz root node provided with STATE,
1245 * follow PATH and return TRUE, iff the REQUIRED access has been granted to
1246 * that user for this PATH. REQUIRED must not contain svn_authz_recursive.
1247 * If RECURSIVE is set, all paths in the sub-tree at and below PATH must
1248 * have REQUIRED access. PATH does not need to be normalized, may be empty
1249 * but must not be NULL.
1250 */
1251 static svn_boolean_t
lookup(lookup_state_t * state,const char * path,authz_access_t required,svn_boolean_t recursive,apr_pool_t * scratch_pool)1252 lookup(lookup_state_t *state,
1253 const char *path,
1254 authz_access_t required,
1255 svn_boolean_t recursive,
1256 apr_pool_t *scratch_pool)
1257 {
1258 /* Create a scratch pad large enough to hold any of PATH's segments. */
1259 apr_size_t path_len = strlen(path);
1260 svn_stringbuf_ensure(state->scratch_pad, path_len);
1261
1262 /* Normalize start and end of PATH. Most paths will be fully normalized,
1263 * so keep the overhead as low as possible. */
1264 if (path_len && path[path_len-1] == '/')
1265 {
1266 do
1267 {
1268 --path_len;
1269 }
1270 while (path_len && path[path_len-1] == '/');
1271 path = apr_pstrmemdup(scratch_pool, path, path_len);
1272 }
1273
1274 while (path[0] == '/')
1275 ++path; /* Don't update PATH_LEN as we won't need it anymore. */
1276
1277 /* Actually walk the path rule tree following PATH until we run out of
1278 * either tree or PATH. */
1279 while (state->current->nelts && path)
1280 {
1281 apr_array_header_t *temp;
1282 int i;
1283 svn_stringbuf_t *segment = state->scratch_pad;
1284
1285 /* Shortcut 1: We could nowhere find enough rights in this sub-tree. */
1286 if ((state->rights.max_rights & required) != required)
1287 return FALSE;
1288
1289 /* Shortcut 2: We will find enough rights everywhere in this sub-tree. */
1290 if ((state->rights.min_rights & required) == required)
1291 return TRUE;
1292
1293 /* Extract the next segment. */
1294 path = next_segment(segment, path);
1295
1296 /* Initial state for this segment. */
1297 apr_array_clear(state->next);
1298 state->rights.access.sequence_number = NO_SEQUENCE_NUMBER;
1299 state->rights.access.rights = authz_access_none;
1300
1301 /* These init values ensure that the first node's value will be used
1302 * when combined with them. If there is no first node,
1303 * state->access.sequence_number remains unchanged and we will use
1304 * the parent's (i.e. inherited) access rights. */
1305 state->rights.min_rights = authz_access_write;
1306 state->rights.max_rights = authz_access_none;
1307
1308 /* Update the PARENT_PATH member in STATE to match the nodes in
1309 * CURRENT at the end of this iteration, i.e. if and when NEXT
1310 * has become CURRENT. */
1311 if (path)
1312 {
1313 svn_stringbuf_appendbyte(state->parent_path, '/');
1314 svn_stringbuf_appendbytes(state->parent_path, segment->data,
1315 segment->len);
1316 }
1317
1318 /* Scan follow all alternative routes to the next level. */
1319 for (i = 0; i < state->current->nelts; ++i)
1320 {
1321 node_t *node = APR_ARRAY_IDX(state->current, i, node_t *);
1322 if (node->sub_nodes)
1323 add_next_node(state, apr_hash_get(node->sub_nodes, segment->data,
1324 segment->len));
1325
1326 /* Process alternative, wildcard-based sub-nodes. */
1327 if (node->pattern_sub_nodes)
1328 {
1329 add_next_node(state, node->pattern_sub_nodes->any);
1330
1331 /* If the current node represents a "**" pattern, it matches
1332 * to all levels. So, add it to the list for the NEXT level. */
1333 if (node->pattern_sub_nodes->repeat)
1334 add_next_node(state, node);
1335
1336 /* Find all prefix pattern matches. */
1337 if (node->pattern_sub_nodes->prefixes)
1338 add_prefix_matches(state, segment,
1339 node->pattern_sub_nodes->prefixes);
1340
1341 if (node->pattern_sub_nodes->complex)
1342 add_complex_matches(state, segment,
1343 node->pattern_sub_nodes->complex);
1344
1345 /* Find all suffux pattern matches.
1346 * This must be the last check as it destroys SEGMENT. */
1347 if (node->pattern_sub_nodes->suffixes)
1348 {
1349 /* Suffixes behave like reversed prefixes. */
1350 svn_authz__reverse_string(segment->data, segment->len);
1351 add_prefix_matches(state, segment,
1352 node->pattern_sub_nodes->suffixes);
1353 }
1354 }
1355 }
1356
1357 /* If no rule applied to this SEGMENT directly, the parent rights
1358 * will apply to at least the SEGMENT node itself and possibly
1359 * other parts deeper in it's subtree. */
1360 if (!has_local_rule(&state->rights))
1361 {
1362 state->rights.access = state->parent_rights.access;
1363 state->rights.min_rights &= state->parent_rights.access.rights;
1364 state->rights.max_rights |= state->parent_rights.access.rights;
1365 }
1366
1367 /* The list of nodes for SEGMENT is now complete. If we need to
1368 * continue, make it the current and put the old one into the recycler.
1369 *
1370 * If this is the end of the path, keep the parent path and rights in
1371 * STATE as are such that sibling lookups will benefit from it.
1372 */
1373 if (path)
1374 {
1375 temp = state->current;
1376 state->current = state->next;
1377 state->next = temp;
1378
1379 /* In STATE, PARENT_PATH, PARENT_RIGHTS and CURRENT are now in sync. */
1380 state->parent_rights = state->rights;
1381 }
1382 }
1383
1384 /* If we check recursively, none of the (potential) sub-paths must have
1385 * less than the REQUIRED access rights. "Potential" because we don't
1386 * verify that the respective paths actually exist in the repository.
1387 */
1388 if (recursive)
1389 return (state->rights.min_rights & required) == required;
1390
1391 /* Return whether the access rights on PATH fully include REQUIRED. */
1392 return (state->rights.access.rights & required) == required;
1393 }
1394
1395
1396
1397 /*** The authz data structure. ***/
1398
1399 /* An entry in svn_authz_t's USER_RULES cache. All members must be
1400 * allocated in the POOL and the latter has to be cleared / destroyed
1401 * before overwriting the entries' contents.
1402 */
1403 struct authz_user_rules_t
1404 {
1405 /* User name for which we filtered the rules.
1406 * User NULL for the anonymous user. */
1407 const char *user;
1408
1409 /* Repository name for which we filtered the rules.
1410 * May be empty but never NULL for used entries. */
1411 const char *repository;
1412
1413 /* The combined min/max rights USER has on REPOSITORY. */
1414 authz_rights_t global_rights;
1415
1416 /* Root of the filtered path rule tree.
1417 * Will remain NULL until the first usage. */
1418 node_t *root;
1419
1420 /* Reusable lookup state instance. */
1421 lookup_state_t *lookup_state;
1422
1423 /* Pool from which all data within this struct got allocated.
1424 * Can be destroyed or cleaned up with no further side-effects. */
1425 apr_pool_t *pool;
1426 };
1427
1428 /* Return TRUE, iff AUTHZ matches the pair of REPOS_NAME and USER.
1429 * Note that USER may be NULL.
1430 */
1431 static svn_boolean_t
matches_filtered_tree(const authz_user_rules_t * authz,const char * repos_name,const char * user)1432 matches_filtered_tree(const authz_user_rules_t *authz,
1433 const char *repos_name,
1434 const char *user)
1435 {
1436 /* Does the user match? */
1437 if (user)
1438 {
1439 if (authz->user == NULL || strcmp(user, authz->user))
1440 return FALSE;
1441 }
1442 else if (authz->user != NULL)
1443 return FALSE;
1444
1445 /* Does the repository match as well? */
1446 return strcmp(repos_name, authz->repository) == 0;
1447 }
1448
1449 /* Check if AUTHZ's already contains a path rule tree filtered for this
1450 * USER, REPOS_NAME combination. If that does not exist, yet, create one
1451 * but don't construct the actual filtered tree, yet.
1452 */
1453 static authz_user_rules_t *
get_user_rules(svn_authz_t * authz,const char * repos_name,const char * user)1454 get_user_rules(svn_authz_t *authz,
1455 const char *repos_name,
1456 const char *user)
1457 {
1458 apr_pool_t *pool;
1459
1460 /* Search our cache for a suitable previously filtered tree. */
1461 if (authz->filtered)
1462 {
1463 /* Is this a suitable filtered tree? */
1464 if (matches_filtered_tree(authz->filtered, repos_name, user))
1465 return authz->filtered;
1466
1467 /* Drop the old filtered tree before creating a new one. */
1468 svn_pool_destroy(authz->filtered->pool);
1469 authz->filtered = NULL;
1470 }
1471
1472 /* Global cache lookup. Filter the full model only if necessary. */
1473 pool = svn_pool_create(authz->pool);
1474
1475 /* Write a new entry. */
1476 authz->filtered = apr_palloc(pool, sizeof(*authz->filtered));
1477 authz->filtered->pool = pool;
1478 authz->filtered->repository = apr_pstrdup(pool, repos_name);
1479 authz->filtered->user = user ? apr_pstrdup(pool, user) : NULL;
1480 authz->filtered->lookup_state = create_lookup_state(pool);
1481 authz->filtered->root = NULL;
1482
1483 svn_authz__get_global_rights(&authz->filtered->global_rights,
1484 authz->full, user, repos_name);
1485
1486 return authz->filtered;
1487 }
1488
1489 /* In AUTHZ's user rules, construct the actual filtered tree.
1490 * Use SCRATCH_POOL for temporary allocations.
1491 */
1492 static svn_error_t *
filter_tree(svn_authz_t * authz,apr_pool_t * scratch_pool)1493 filter_tree(svn_authz_t *authz,
1494 apr_pool_t *scratch_pool)
1495 {
1496 apr_pool_t *pool = authz->filtered->pool;
1497 const char *repos_name = authz->filtered->repository;
1498 const char *user = authz->filtered->user;
1499 node_t *root;
1500
1501 if (filtered_pool)
1502 {
1503 svn_membuf_t *key = construct_filtered_key(repos_name, user,
1504 authz->authz_id,
1505 scratch_pool);
1506
1507 /* Cache lookup. */
1508 SVN_ERR(svn_object_pool__lookup((void **)&root, filtered_pool, key,
1509 pool));
1510
1511 if (!root)
1512 {
1513 apr_pool_t *item_pool = svn_object_pool__new_item_pool(authz_pool);
1514 authz_full_t *add_ref = NULL;
1515
1516 /* Make sure the underlying full authz object lives as long as the
1517 * filtered one that we are about to create. We do this by adding
1518 * a reference to it in ITEM_POOL (which may live longer than AUTHZ).
1519 *
1520 * Note that we already have a reference to that full authz in
1521 * AUTHZ->FULL. Assert that we actually don't created multiple
1522 * instances of the same full model.
1523 */
1524 svn_error_clear(svn_object_pool__lookup((void **)&add_ref,
1525 authz_pool, authz->authz_id,
1526 item_pool));
1527 SVN_ERR_ASSERT(add_ref == authz->full);
1528
1529 /* Now construct the new filtered tree and cache it. */
1530 root = create_user_authz(authz->full, repos_name, user, item_pool,
1531 scratch_pool);
1532 svn_error_clear(svn_object_pool__insert((void **)&root,
1533 filtered_pool, key, root,
1534 item_pool, pool));
1535 }
1536 }
1537 else
1538 {
1539 root = create_user_authz(authz->full, repos_name, user, pool,
1540 scratch_pool);
1541 }
1542
1543 /* Write a new entry. */
1544 authz->filtered->root = root;
1545
1546 return SVN_NO_ERROR;
1547 }
1548
1549
1550
1551 /* Read authz configuration data from PATH into *AUTHZ_P, allocated in
1552 RESULT_POOL. Return the cache key in *AUTHZ_ID. If GROUPS_PATH is set,
1553 use the global groups parsed from it. Use SCRATCH_POOL for temporary
1554 allocations.
1555
1556 PATH and GROUPS_PATH may be a dirent or an absolute file url. REPOS_HINT
1557 may be specified to speed up access to in-repo authz files.
1558
1559 If PATH or GROUPS_PATH is not a valid authz rule file, then return
1560 SVN_AUTHZ_INVALID_CONFIG. The contents of *AUTHZ_P is then
1561 undefined. If MUST_EXIST is TRUE, a missing authz or global groups file
1562 is also an error. */
1563 static svn_error_t *
authz_read(authz_full_t ** authz_p,svn_membuf_t ** authz_id,const char * path,const char * groups_path,svn_boolean_t must_exist,svn_repos_t * repos_hint,svn_repos_authz_warning_func_t warning_func,void * warning_baton,apr_pool_t * result_pool,apr_pool_t * scratch_pool)1564 authz_read(authz_full_t **authz_p,
1565 svn_membuf_t **authz_id,
1566 const char *path,
1567 const char *groups_path,
1568 svn_boolean_t must_exist,
1569 svn_repos_t *repos_hint,
1570 svn_repos_authz_warning_func_t warning_func,
1571 void *warning_baton,
1572 apr_pool_t *result_pool,
1573 apr_pool_t *scratch_pool)
1574 {
1575 svn_error_t* err = NULL;
1576 svn_stream_t *rules_stream = NULL;
1577 svn_stream_t *groups_stream = NULL;
1578 svn_checksum_t *rules_checksum = NULL;
1579 svn_checksum_t *groups_checksum = NULL;
1580
1581 config_access_t *config_access =
1582 svn_repos__create_config_access(repos_hint, scratch_pool);
1583
1584 /* Open the main authz file */
1585 SVN_ERR(svn_repos__get_config(&rules_stream, &rules_checksum, config_access,
1586 path, must_exist, scratch_pool));
1587
1588 /* Open the optional groups file */
1589 if (groups_path)
1590 SVN_ERR(svn_repos__get_config(&groups_stream, &groups_checksum,
1591 config_access, groups_path, must_exist,
1592 scratch_pool));
1593
1594 /* The authz cache is optional. */
1595 *authz_id = construct_authz_key(rules_checksum, groups_checksum,
1596 result_pool);
1597 if (authz_pool)
1598 {
1599 /* Cache lookup. */
1600 SVN_ERR(svn_object_pool__lookup((void **)authz_p, authz_pool,
1601 *authz_id, result_pool));
1602
1603 /* If not found, parse and add to cache. */
1604 if (!*authz_p)
1605 {
1606 apr_pool_t *item_pool = svn_object_pool__new_item_pool(authz_pool);
1607
1608 /* Parse the configuration(s) and construct the full authz model
1609 * from it. */
1610 err = svn_authz__parse(authz_p, rules_stream, groups_stream,
1611 warning_func, warning_baton,
1612 item_pool, scratch_pool);
1613 if (err != SVN_NO_ERROR)
1614 {
1615 /* That pool would otherwise never get destroyed. */
1616 svn_pool_destroy(item_pool);
1617
1618 /* Add the URL / file name to the error stack since the parser
1619 * doesn't have it. */
1620 err = svn_error_quick_wrapf(err,
1621 "Error while parsing config file: '%s':",
1622 path);
1623 }
1624 else
1625 {
1626 SVN_ERR(svn_object_pool__insert((void **)authz_p, authz_pool,
1627 *authz_id, *authz_p,
1628 item_pool, result_pool));
1629 }
1630 }
1631 }
1632 else
1633 {
1634 /* Parse the configuration(s) and construct the full authz model from
1635 * it. */
1636 err = svn_error_quick_wrapf(
1637 svn_authz__parse(authz_p, rules_stream, groups_stream,
1638 warning_func, warning_baton,
1639 result_pool, scratch_pool),
1640 "Error while parsing authz file: '%s':", path);
1641 }
1642
1643 svn_repos__destroy_config_access(config_access);
1644
1645 return err;
1646 }
1647
1648
1649
1650 /*** Public functions. ***/
1651
1652 svn_error_t *
svn_repos_authz_read4(svn_authz_t ** authz_p,const char * path,const char * groups_path,svn_boolean_t must_exist,svn_repos_t * repos_hint,svn_repos_authz_warning_func_t warning_func,void * warning_baton,apr_pool_t * result_pool,apr_pool_t * scratch_pool)1653 svn_repos_authz_read4(svn_authz_t **authz_p,
1654 const char *path,
1655 const char *groups_path,
1656 svn_boolean_t must_exist,
1657 svn_repos_t *repos_hint,
1658 svn_repos_authz_warning_func_t warning_func,
1659 void *warning_baton,
1660 apr_pool_t *result_pool,
1661 apr_pool_t *scratch_pool)
1662 {
1663 svn_authz_t *authz = apr_pcalloc(result_pool, sizeof(*authz));
1664 authz->pool = result_pool;
1665
1666 SVN_ERR(authz_read(&authz->full, &authz->authz_id, path, groups_path,
1667 must_exist, repos_hint, warning_func, warning_baton,
1668 result_pool, scratch_pool));
1669
1670 *authz_p = authz;
1671 return SVN_NO_ERROR;
1672 }
1673
1674
1675 svn_error_t *
svn_repos_authz_parse2(svn_authz_t ** authz_p,svn_stream_t * stream,svn_stream_t * groups_stream,svn_repos_authz_warning_func_t warning_func,void * warning_baton,apr_pool_t * result_pool,apr_pool_t * scratch_pool)1676 svn_repos_authz_parse2(svn_authz_t **authz_p,
1677 svn_stream_t *stream,
1678 svn_stream_t *groups_stream,
1679 svn_repos_authz_warning_func_t warning_func,
1680 void *warning_baton,
1681 apr_pool_t *result_pool,
1682 apr_pool_t *scratch_pool)
1683 {
1684 svn_authz_t *authz = apr_pcalloc(result_pool, sizeof(*authz));
1685 authz->pool = result_pool;
1686
1687 /* Parse the configuration and construct the full authz model from it. */
1688 SVN_ERR(svn_authz__parse(&authz->full, stream, groups_stream,
1689 warning_func, warning_baton,
1690 result_pool, scratch_pool));
1691
1692 *authz_p = authz;
1693 return SVN_NO_ERROR;
1694 }
1695
1696 svn_error_t *
svn_repos_authz_check_access(svn_authz_t * authz,const char * repos_name,const char * path,const char * user,svn_repos_authz_access_t required_access,svn_boolean_t * access_granted,apr_pool_t * pool)1697 svn_repos_authz_check_access(svn_authz_t *authz, const char *repos_name,
1698 const char *path, const char *user,
1699 svn_repos_authz_access_t required_access,
1700 svn_boolean_t *access_granted,
1701 apr_pool_t *pool)
1702 {
1703 const authz_access_t required =
1704 ((required_access & svn_authz_read ? authz_access_read_flag : 0)
1705 | (required_access & svn_authz_write ? authz_access_write_flag : 0));
1706
1707 /* Pick or create the suitable pre-filtered path rule tree. */
1708 authz_user_rules_t *rules = get_user_rules(
1709 authz,
1710 (repos_name ? repos_name : AUTHZ_ANY_REPOSITORY),
1711 user);
1712
1713 /* In many scenarios, users have uniform access to a repository
1714 * (blanket access or no access at all).
1715 *
1716 * In these cases, don't bother creating or consulting the filtered tree.
1717 */
1718 if ((rules->global_rights.min_access & required) == required)
1719 {
1720 *access_granted = TRUE;
1721 return SVN_NO_ERROR;
1722 }
1723
1724 if ((rules->global_rights.max_access & required) != required)
1725 {
1726 *access_granted = FALSE;
1727 return SVN_NO_ERROR;
1728 }
1729
1730 /* No specific path given, i.e. looking for anywhere in the tree? */
1731 if (!path)
1732 {
1733 *access_granted =
1734 ((rules->global_rights.max_access & required) == required);
1735 return SVN_NO_ERROR;
1736 }
1737
1738 /* Rules tree lookup */
1739
1740 /* Did we already filter the data model? */
1741 if (!rules->root)
1742 SVN_ERR(filter_tree(authz, pool));
1743
1744 /* Re-use previous lookup results, if possible. */
1745 path = init_lockup_state(authz->filtered->lookup_state,
1746 authz->filtered->root, path);
1747
1748 /* Sanity check. */
1749 SVN_ERR_ASSERT(path[0] == '/');
1750
1751 /* Determine the granted access for the requested path.
1752 * PATH does not need to be normalized for lockup(). */
1753 *access_granted = lookup(rules->lookup_state, path, required,
1754 !!(required_access & svn_authz_recursive), pool);
1755
1756 return SVN_NO_ERROR;
1757 }
1758