Misc. fixes
[wimlib] / src / security.c
1 /*
2  * security.c
3  *
4  * Read and write the per-WIM-image table of security descriptors.
5  */
6
7 /*
8  * Copyright (C) 2012, 2013 Eric Biggers
9  *
10  * This file is part of wimlib, a library for working with WIM files.
11  *
12  * wimlib is free software; you can redistribute it and/or modify it under the
13  * terms of the GNU General Public License as published by the Free
14  * Software Foundation; either version 3 of the License, or (at your option)
15  * any later version.
16  *
17  * wimlib is distributed in the hope that it will be useful, but WITHOUT ANY
18  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
19  * A PARTICULAR PURPOSE. See the GNU General Public License for more
20  * details.
21  *
22  * You should have received a copy of the GNU General Public License
23  * along with wimlib; if not, see http://www.gnu.org/licenses/.
24  */
25
26 #include "wimlib_internal.h"
27 #include "buffer_io.h"
28 #include "security.h"
29
30
31 #define SECURITY_DESCRIPTOR_REVISION    1
32 #define SECURITY_DESCRIPTOR_REVISION1   1
33
34 /* inherit AceFlags */
35 #define OBJECT_INHERIT_ACE              0x01
36 #define CONTAINER_INHERIT_ACE           0x02
37 #define NO_PROPAGATE_INHERIT_ACE        0x04
38 #define INHERIT_ONLY_ACE                0x08
39 #define INHERITED_ACE                   0x10
40 #define VALID_INHERIT_FLAGS             0x1F
41
42 #define SE_OWNER_DEFAULTED              0x00000001
43 #define SE_GROUP_DEFAULTED              0x00000002
44 #define SE_DACL_PRESENT                 0x00000004
45 #define SE_DACL_DEFAULTED               0x00000008
46 #define SE_SACL_PRESENT                 0x00000010
47 #define SE_SACL_DEFAULTED               0x00000020
48 #define SE_DACL_AUTO_INHERIT_REQ        0x00000100
49 #define SE_SACL_AUTO_INHERIT_REQ        0x00000200
50 #define SE_DACL_AUTO_INHERITED          0x00000400
51 #define SE_SACL_AUTO_INHERITED          0x00000800
52 #define SE_DACL_PROTECTED               0x00001000
53 #define SE_SACL_PROTECTED               0x00002000
54 #define SE_RM_CONTROL_VALID             0x00004000
55 #define SE_SELF_RELATIVE                0x00008000
56
57 /* Flags in access control entries */
58 #define DELETE                     0x00010000
59 #define READ_CONTROL               0x00020000
60 #define WRITE_DAC                  0x00040000
61 #define WRITE_OWNER                0x00080000
62 #define SYNCHRONIZE                0x00100000
63 #define STANDARD_RIGHTS_REQUIRED   0x000f0000
64
65 #define STANDARD_RIGHTS_READ       READ_CONTROL
66 #define STANDARD_RIGHTS_WRITE      READ_CONTROL
67 #define STANDARD_RIGHTS_EXECUTE    READ_CONTROL
68
69 #define STANDARD_RIGHTS_ALL        0x001f0000
70
71 #define SPECIFIC_RIGHTS_ALL        0x0000ffff
72
73 #define GENERIC_READ               0x80000000
74 #define GENERIC_WRITE              0x40000000
75 #define GENERIC_EXECUTE            0x20000000
76 #define GENERIC_ALL                0x10000000
77
78 #define MAXIMUM_ALLOWED            0x02000000
79 #define ACCESS_SYSTEM_SECURITY     0x01000000
80
81 #define EVENT_QUERY_STATE          0x0001
82 #define EVENT_MODIFY_STATE         0x0002
83 #define EVENT_ALL_ACCESS           (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0x3)
84
85 #define SEMAPHORE_MODIFY_STATE     0x0002
86 #define SEMAPHORE_ALL_ACCESS       (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0x3)
87
88 #define MUTEX_MODIFY_STATE         0x0001
89 #define MUTEX_ALL_ACCESS           (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0x1)
90
91 #define JOB_OBJECT_ASSIGN_PROCESS           0x0001
92 #define JOB_OBJECT_SET_ATTRIBUTES           0x0002
93 #define JOB_OBJECT_QUERY                    0x0004
94 #define JOB_OBJECT_TERMINATE                0x0008
95 #define JOB_OBJECT_SET_SECURITY_ATTRIBUTES  0x0010
96 #define JOB_OBJECT_ALL_ACCESS               (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0x1f)
97
98 #define TIMER_QUERY_STATE          0x0001
99 #define TIMER_MODIFY_STATE         0x0002
100 #define TIMER_ALL_ACCESS           (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0x3)
101
102 #define PROCESS_TERMINATE          0x0001
103 #define PROCESS_CREATE_THREAD      0x0002
104 #define PROCESS_VM_OPERATION       0x0008
105 #define PROCESS_VM_READ            0x0010
106 #define PROCESS_VM_WRITE           0x0020
107 #define PROCESS_DUP_HANDLE         0x0040
108 #define PROCESS_CREATE_PROCESS     0x0080
109 #define PROCESS_SET_QUOTA          0x0100
110 #define PROCESS_SET_INFORMATION    0x0200
111 #define PROCESS_QUERY_INFORMATION  0x0400
112 #define PROCESS_SUSPEND_RESUME     0x0800
113 #define PROCESS_QUERY_LIMITED_INFORMATION 0x1000
114 #define PROCESS_ALL_ACCESS         (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0xfff)
115
116 #define THREAD_TERMINATE           0x0001
117 #define THREAD_SUSPEND_RESUME      0x0002
118 #define THREAD_GET_CONTEXT         0x0008
119 #define THREAD_SET_CONTEXT         0x0010
120 #define THREAD_SET_INFORMATION     0x0020
121 #define THREAD_QUERY_INFORMATION   0x0040
122 #define THREAD_SET_THREAD_TOKEN    0x0080
123 #define THREAD_IMPERSONATE         0x0100
124 #define THREAD_DIRECT_IMPERSONATION 0x0200
125 #define THREAD_ALL_ACCESS          (STANDARD_RIGHTS_REQUIRED|SYNCHRONIZE|0x3ff)
126
127 #define THREAD_BASE_PRIORITY_LOWRT  15
128 #define THREAD_BASE_PRIORITY_MAX    2
129 #define THREAD_BASE_PRIORITY_MIN   -2
130 #define THREAD_BASE_PRIORITY_IDLE  -15
131
132 /* predefined authority values for SID's (security identifiers) */
133 enum sid_authority_value {
134         SECURITY_NULL_SID_AUTHORITY    = 0,
135         SECURITY_WORLD_SID_AUTHORITY   = 1,
136         SECURITY_LOCAL_SID_AUTHORITY   = 2,
137         SECURITY_CREATOR_SID_AUTHORITY = 3,
138         SECURITY_NON_UNIQUE_AUTHORITY  = 4,
139         SECURITY_NT_AUTHORITY          = 5,
140 };
141
142 /* local administrators group */
143 #define SECURITY_BUILTIN_DOMAIN_RID 32
144 #define DOMAIN_ALIAS_RID_ADMINS     544
145
146 /* See ACEHeader. */
147 enum ace_type {
148         ACCESS_ALLOWED_ACE_TYPE = 0,
149         ACCESS_DENIED_ACE_TYPE  = 1,
150         SYSTEM_AUDIT_ACE_TYPE   = 2,
151 };
152
153 /* At the start of each type of access control entry.  */
154 typedef struct {
155         /* enum ace_type, specifies what type of ACE this is.  */
156         u8 type;
157
158         /* bitwise OR of the inherit ACE flags #defined above */
159         u8 flags;
160
161         /* Size of the access control entry. */
162         u8 size;
163 } ACEHeader;
164
165 /* Grants rights to a user or group */
166 typedef struct {
167         ACEHeader hdr;
168         u32 mask;
169         u32 sid_start;
170 } AccessAllowedACE;
171
172 /* Denies rights to a user or group */
173 typedef struct {
174         ACEHeader hdr;
175         u32 mask;
176         u32 sid_start;
177 } AccessDeniedACE;
178
179 typedef struct {
180         ACEHeader hdr;
181         u32 mask;
182         u32 sid_start;
183 } SystemAuditACE;
184
185
186 /* Header of an access control list. */
187 typedef struct {
188         /* ACL_REVISION or ACL_REVISION_DS */
189         u8 revision;
190
191         /* padding */
192         u8 sbz1;
193
194         /* Total size of the ACL, including all access control entries */
195         u16 acl_size;
196
197         /* Number of access control entry structures that follow the ACL
198          * structure. */
199         u16 ace_count;
200
201         /* padding */
202         u16 sbz2;
203 } ACL;
204
205 /* A structure used to identify users or groups. */
206 typedef struct {
207
208         /* example: 0x1 */
209         u8  revision;
210         u8  sub_authority_count;
211
212         /* Identifies the authority that issued the SID.  Can be, but does not
213          * have to be, one of enum sid_authority_value */
214         u8  identifier_authority[6];
215
216         u32 sub_authority[0];
217 } SID;
218
219
220 typedef struct {
221         /* Example: 0x1 */
222         u8 revision;
223         /* Example: 0x0 */
224         u8 sbz1;
225         /* Example: 0x4149 */
226         u16 security_descriptor_control;
227
228         /* Offset of a SID structure in the security descriptor. */
229         /* Example: 0x14 */
230         u32 owner_offset;
231
232         /* Offset of a SID structure in the security descriptor. */
233         /* Example: 0x24 */
234         u32 group_offset;
235
236         /* Offset of an ACL structure in the security descriptor. */
237         /* System ACL. */
238         /* Example: 0x00 */
239         u32 sacl_offset;
240
241         /* Offset of an ACL structure in the security descriptor. */
242         /* Discretionary ACL. */
243         /* Example: 0x34 */
244         u32 dacl_offset;
245 } SecurityDescriptor;
246
247 /*
248  * This is a hack to work around a problem in libntfs-3g.  libntfs-3g validates
249  * security descriptors with a function named ntfs_valid_descr().
250  * ntfs_valid_descr() considers a security descriptor that ends in a SACL
251  * (Sysetm Access Control List) with no ACE's (Access Control Entries) to be
252  * invalid.  However, a security descriptor like this exists in the Windows 7
253  * install.wim.  Here, security descriptors matching this pattern are modified
254  * to have no SACL.  This should make no difference since the SACL had no
255  * entries anyway; however this ensures that that the security descriptors pass
256  * the validation in libntfs-3g.
257  */
258 static void
259 empty_sacl_fixup(u8 *descr, u64 *size_p)
260 {
261         /* No-op if no NTFS-3g support, or if NTFS-3g is version 2013 or later
262          * */
263 #if defined(WITH_NTFS_3G) && !defined(HAVE_NTFS_MNT_RDONLY)
264         if (*size_p >= sizeof(SecurityDescriptor)) {
265                 SecurityDescriptor *sd = (SecurityDescriptor*)descr;
266                 u32 sacl_offset = le32_to_cpu(sd->sacl_offset);
267                 if (sacl_offset == *size_p - sizeof(ACL)) {
268                         sd->sacl_offset = cpu_to_le32(0);
269                         *size_p -= sizeof(ACL);
270                 }
271         }
272 #endif
273 }
274
275 /*
276  * Reads the security data from the metadata resource.
277  *
278  * @metadata_resource:  An array that contains the uncompressed metadata
279  *                              resource for the WIM file.
280  * @metadata_resource_len:      The length of @metadata_resource.  It must be at
281  *                              least 8 bytes.
282  * @sd_p:       A pointer to a pointer to a wim_security_data structure that
283  *              will be filled in with a pointer to a new wim_security_data
284  *              structure on success.
285  *
286  * Note: There is no `offset' argument because the security data is located at
287  * the beginning of the metadata resource.
288  */
289 int
290 read_security_data(const u8 metadata_resource[], u64 metadata_resource_len,
291                    struct wim_security_data **sd_p)
292 {
293         struct wim_security_data *sd;
294         const u8 *p;
295         int ret;
296         u64 total_len;
297
298         wimlib_assert(metadata_resource_len >= 8);
299
300         /*
301          * Sorry this function is excessively complicated--- I'm just being
302          * extremely careful about integer overflows.
303          */
304
305         sd = MALLOC(sizeof(struct wim_security_data));
306         if (!sd) {
307                 ERROR("Out of memory");
308                 return WIMLIB_ERR_NOMEM;
309         }
310         sd->sizes       = NULL;
311         sd->descriptors = NULL;
312         sd->refcnt      = 1;
313
314         p = metadata_resource;
315         p = get_u32(p, &sd->total_length);
316         p = get_u32(p, (u32*)&sd->num_entries);
317
318         /* The security_id field of each dentry is a signed 32-bit integer, so
319          * the possible indices into the security descriptors table are 0
320          * through 0x7fffffff.  Which means 0x80000000 security descriptors
321          * maximum.  Not like you should ever have anywhere close to that many
322          * security descriptors! */
323         if (sd->num_entries > 0x80000000) {
324                 ERROR("Security data has too many entries!");
325                 goto out_invalid_sd;
326         }
327
328         /* Verify the listed total length of the security data is big enough to
329          * include the sizes array, verify that the file data is big enough to
330          * include it as well, then allocate the array of sizes.
331          *
332          * Note: The total length of the security data must fit in a 32-bit
333          * integer, even though each security descriptor size is a 64-bit
334          * integer.  This is stupid, and we need to be careful not to actually
335          * let the security descriptor sizes be over 0xffffffff.  */
336         if ((u64)sd->total_length > metadata_resource_len) {
337                 ERROR("Security data total length (%u) is bigger than the "
338                       "metadata resource length (%"PRIu64")",
339                       sd->total_length, metadata_resource_len);
340                 goto out_invalid_sd;
341         }
342
343         DEBUG("Reading security data: %u entries, length = %u",
344               sd->num_entries, sd->total_length);
345
346         if (sd->num_entries == 0) {
347                 /* No security descriptors.  We allow the total_length field to
348                  * be either 8 (which is correct, since there are always 2
349                  * 32-bit integers) or 0. */
350                 if (sd->total_length != 0 && sd->total_length != 8) {
351                         ERROR("Invalid security data length (%u): expected 0 or 8",
352                               sd->total_length);
353                         goto out_invalid_sd;
354                 }
355                 sd->total_length = 8;
356                 goto out_return_sd;
357         }
358
359         u64 sizes_size = (u64)sd->num_entries * sizeof(u64);
360         u64 size_no_descriptors = 8 + sizes_size;
361         if (size_no_descriptors > (u64)sd->total_length) {
362                 ERROR("Security data total length of %u is too short because "
363                       "there seem to be at least %"PRIu64" bytes of security data",
364                       sd->total_length, 8 + sizes_size);
365                 goto out_invalid_sd;
366         }
367
368         sd->sizes = MALLOC(sizes_size);
369         if (!sd->sizes) {
370                 ret = WIMLIB_ERR_NOMEM;
371                 goto out_free_sd;
372         }
373
374         /* Copy the sizes array in from the file data. */
375         p = get_bytes(p, sizes_size, sd->sizes);
376         array_le64_to_cpu(sd->sizes, sd->num_entries);
377
378         /* Allocate the array of pointers to descriptors, and read them in. */
379         sd->descriptors = CALLOC(sd->num_entries, sizeof(u8*));
380         if (!sd->descriptors) {
381                 ERROR("Out of memory while allocating security "
382                       "descriptors");
383                 ret = WIMLIB_ERR_NOMEM;
384                 goto out_free_sd;
385         }
386         total_len = size_no_descriptors;
387
388         for (u32 i = 0; i < sd->num_entries; i++) {
389                 /* Watch out for huge security descriptor sizes that could
390                  * overflow the total length and wrap it around. */
391                 if (total_len + sd->sizes[i] < total_len) {
392                         ERROR("Caught overflow in security descriptor lengths "
393                               "(current total length = %"PRIu64", security "
394                               "descriptor size = %"PRIu64")",
395                               total_len, sd->sizes[i]);
396                         goto out_invalid_sd;
397                 }
398                 total_len += sd->sizes[i];
399                 /* This check ensures that the descriptor size fits in a 32 bit
400                  * integer.  Because if it didn't, the total length would come
401                  * out bigger than sd->total_length, which is a 32 bit integer.
402                  * */
403                 if (total_len > (u64)sd->total_length) {
404                         ERROR("Security data total length of %u is too short "
405                               "because there seem to be at least %"PRIu64" "
406                               "bytes of security data",
407                               sd->total_length, total_len);
408                         goto out_invalid_sd;
409                 }
410                 sd->descriptors[i] = MALLOC(sd->sizes[i]);
411                 if (!sd->descriptors[i]) {
412                         ERROR("Out of memory while allocating security "
413                               "descriptors");
414                         ret = WIMLIB_ERR_NOMEM;
415                         goto out_free_sd;
416                 }
417                 p = get_bytes(p, sd->sizes[i], sd->descriptors[i]);
418                 empty_sacl_fixup(sd->descriptors[i], &sd->sizes[i]);
419         }
420         wimlib_assert(total_len <= 0xffffffff);
421         if (((total_len + 7) & ~7) != ((sd->total_length + 7) & ~7)) {
422                 ERROR("Expected security data total length = %u, but "
423                       "calculated %u", sd->total_length, (unsigned)total_len);
424                 goto out_invalid_sd;
425         }
426         sd->total_length = total_len;
427 out_return_sd:
428         *sd_p = sd;
429         return 0;
430 out_invalid_sd:
431         ret = WIMLIB_ERR_INVALID_SECURITY_DATA;
432 out_free_sd:
433         free_security_data(sd);
434         return ret;
435 }
436
437 /*
438  * Writes security data to an in-memory buffer.
439  */
440 u8 *
441 write_security_data(const struct wim_security_data *sd, u8 *p)
442 {
443         DEBUG("Writing security data (total_length = %"PRIu32", num_entries "
444               "= %"PRIu32")", sd->total_length, sd->num_entries);
445
446         u32 aligned_length = (sd->total_length + 7) & ~7;
447
448         u8 *orig_p = p;
449         p = put_u32(p, aligned_length);
450         p = put_u32(p, sd->num_entries);
451
452         for (u32 i = 0; i < sd->num_entries; i++)
453                 p = put_u64(p, sd->sizes[i]);
454
455         for (u32 i = 0; i < sd->num_entries; i++)
456                 p = put_bytes(p, sd->sizes[i], sd->descriptors[i]);
457
458         wimlib_assert(p - orig_p == sd->total_length);
459         p = put_zeroes(p, aligned_length - sd->total_length);
460
461         DEBUG("Successfully wrote security data.");
462         return p;
463 }
464
465 static void
466 print_acl(const u8 *p, const char *type)
467 {
468         const ACL *acl = (const ACL*)p;
469         u8 revision = acl->revision;
470         u16 acl_size = le16_to_cpu(acl->acl_size);
471         u16 ace_count = le16_to_cpu(acl->ace_count);
472         printf("    [%s ACL]\n", type);
473         printf("    Revision = %u\n", revision);
474         printf("    ACL Size = %u\n", acl_size);
475         printf("    ACE Count = %u\n", ace_count);
476
477         p += sizeof(ACL);
478         for (u16 i = 0; i < ace_count; i++) {
479                 const ACEHeader *hdr = (const ACEHeader*)p;
480                 printf("        [ACE]\n");
481                 printf("        ACE type  = %d\n", hdr->type);
482                 printf("        ACE flags = 0x%x\n", hdr->flags);
483                 printf("        ACE size  = %u\n", hdr->size);
484                 const AccessAllowedACE *aaa = (const AccessAllowedACE*)hdr;
485                 printf("        ACE mask = %x\n", le32_to_cpu(aaa->mask));
486                 printf("        SID start = %u\n", le32_to_cpu(aaa->sid_start));
487                 p += hdr->size;
488         }
489         putchar('\n');
490 }
491
492 static void
493 print_sid(const u8 *p, const char *type)
494 {
495         const SID *sid = (const SID*)p;
496         printf("    [%s SID]\n", type);
497         printf("    Revision = %u\n", sid->revision);
498         printf("    Subauthority count = %u\n", sid->sub_authority_count);
499         printf("    Identifier authority = ");
500         print_byte_field(sid->identifier_authority,
501                          sizeof(sid->identifier_authority));
502         putchar('\n');
503         for (u8 i = 0; i < sid->sub_authority_count; i++)
504                 printf("    Subauthority %u = %u\n",
505                        i, le32_to_cpu(sid->sub_authority[i]));
506         putchar('\n');
507 }
508
509 static void
510 print_security_descriptor(const u8 *p, u64 size)
511 {
512         const SecurityDescriptor *sd = (const SecurityDescriptor*)p;
513         u8 revision      = sd->revision;
514         u16 control      = le16_to_cpu(sd->security_descriptor_control);
515         u32 owner_offset = le32_to_cpu(sd->owner_offset);
516         u32 group_offset = le32_to_cpu(sd->group_offset);
517         u32 sacl_offset  = le32_to_cpu(sd->sacl_offset);
518         u32 dacl_offset  = le32_to_cpu(sd->dacl_offset);
519         printf("Revision = %u\n", revision);
520         printf("Security Descriptor Control = %#x\n", control);
521         printf("Owner offset = %u\n", owner_offset);
522         printf("Group offset = %u\n", group_offset);
523         printf("System ACL offset = %u\n", sacl_offset);
524         printf("Discretionary ACL offset = %u\n", dacl_offset);
525
526         if (sd->owner_offset != 0)
527                 print_sid(p + owner_offset, "Owner");
528         if (sd->group_offset != 0)
529                 print_sid(p + group_offset, "Group");
530         if (sd->sacl_offset != 0)
531                 print_acl(p + sacl_offset, "System");
532         if (sd->dacl_offset != 0)
533                 print_acl(p + dacl_offset, "Discretionary");
534 }
535
536 /*
537  * Prints the security data for a WIM file.
538  */
539 void
540 print_security_data(const struct wim_security_data *sd)
541 {
542         wimlib_assert(sd != NULL);
543
544         puts("[SECURITY DATA]");
545         printf("Length            = %"PRIu32" bytes\n", sd->total_length);
546         printf("Number of Entries = %"PRIu32"\n", sd->num_entries);
547
548         for (u32 i = 0; i < sd->num_entries; i++) {
549                 printf("[SecurityDescriptor %"PRIu32", length = %"PRIu64"]\n",
550                        i, sd->sizes[i]);
551                 print_security_descriptor(sd->descriptors[i], sd->sizes[i]);
552                 putchar('\n');
553         }
554         putchar('\n');
555 }
556
557 void
558 free_security_data(struct wim_security_data *sd)
559 {
560         if (sd) {
561                 wimlib_assert(sd->refcnt != 0);
562                 if (--sd->refcnt == 0) {
563                         u8 **descriptors = sd->descriptors;
564                         u32 num_entries  = sd->num_entries;
565                         if (descriptors)
566                                 while (num_entries--)
567                                         FREE(*descriptors++);
568                         FREE(sd->sizes);
569                         FREE(sd->descriptors);
570                         FREE(sd);
571                 }
572         }
573 }
574
575 /* The security tree stuff is only needed when NTFS capture is supported, either
576  * through NTFS-3G or through a native Windows build. */
577 #if defined(WITH_NTFS_3G) || defined(__WIN32__)
578 struct sd_node {
579         int security_id;
580         u8 hash[SHA1_HASH_SIZE];
581         struct rb_node rb_node;
582 };
583
584 static void
585 free_sd_tree(struct rb_node *node)
586 {
587         if (node) {
588                 free_sd_tree(node->rb_left);
589                 free_sd_tree(node->rb_right);
590                 FREE(container_of(node, struct sd_node, rb_node));
591         }
592 }
593
594 /* Frees a security descriptor index set. */
595 void
596 destroy_sd_set(struct sd_set *sd_set)
597 {
598         free_sd_tree(sd_set->rb_root.rb_node);
599 }
600
601 /* Inserts a a new node into the security descriptor index tree. */
602 static void
603 insert_sd_node(struct sd_set *set, struct sd_node *new)
604 {
605         struct rb_root *root = &set->rb_root;
606         struct rb_node **p = &(root->rb_node);
607         struct rb_node *rb_parent = NULL;
608
609         while (*p) {
610                 struct sd_node *this = container_of(*p, struct sd_node, rb_node);
611                 int cmp = hashes_cmp(new->hash, this->hash);
612
613                 rb_parent = *p;
614                 if (cmp < 0)
615                         p = &((*p)->rb_left);
616                 else if (cmp > 0)
617                         p = &((*p)->rb_right);
618                 else
619                         wimlib_assert(0); /* Duplicate SHA1 message digest */
620         }
621         rb_link_node(&new->rb_node, rb_parent, p);
622         rb_insert_color(&new->rb_node, root);
623 }
624
625 /* Returns the index of the security descriptor having a SHA1 message digest of
626  * @hash.  If not found, return -1. */
627 int
628 lookup_sd(struct sd_set *set, const u8 hash[SHA1_HASH_SIZE])
629 {
630         struct rb_node *node = set->rb_root.rb_node;
631
632         while (node) {
633                 struct sd_node *sd_node = container_of(node, struct sd_node, rb_node);
634                 int cmp = hashes_cmp(hash, sd_node->hash);
635                 if (cmp < 0)
636                         node = node->rb_left;
637                 else if (cmp > 0)
638                         node = node->rb_right;
639                 else
640                         return sd_node->security_id;
641         }
642         return -1;
643 }
644
645 /*
646  * Adds a security descriptor to the indexed security descriptor set as well as
647  * the corresponding `struct wim_security_data', and returns the new security
648  * ID; or, if there is an existing security descriptor that is the same, return
649  * the security ID for it.  If a new security descriptor cannot be allocated,
650  * return -1.
651  */
652 int
653 sd_set_add_sd(struct sd_set *sd_set, const char descriptor[], size_t size)
654 {
655         u8 hash[SHA1_HASH_SIZE];
656         int security_id;
657         struct sd_node *new;
658         u8 **descriptors;
659         u64 *sizes;
660         u8 *descr_copy;
661         struct wim_security_data *sd;
662
663         sha1_buffer((const u8*)descriptor, size, hash);
664
665         security_id = lookup_sd(sd_set, hash);
666         if (security_id >= 0) /* Identical descriptor already exists */
667                 return security_id;
668
669         /* Need to add a new security descriptor */
670         new = MALLOC(sizeof(*new));
671         if (!new)
672                 goto out;
673         descr_copy = MALLOC(size);
674         if (!descr_copy)
675                 goto out_free_node;
676
677         sd = sd_set->sd;
678
679         memcpy(descr_copy, descriptor, size);
680         new->security_id = sd->num_entries;
681         copy_hash(new->hash, hash);
682
683         descriptors = REALLOC(sd->descriptors,
684                               (sd->num_entries + 1) * sizeof(sd->descriptors[0]));
685         if (!descriptors)
686                 goto out_free_descr;
687         sd->descriptors = descriptors;
688         sizes = REALLOC(sd->sizes,
689                         (sd->num_entries + 1) * sizeof(sd->sizes[0]));
690         if (!sizes)
691                 goto out_free_descr;
692         sd->sizes = sizes;
693         sd->descriptors[sd->num_entries] = descr_copy;
694         sd->sizes[sd->num_entries] = size;
695         sd->num_entries++;
696         DEBUG("There are now %d security descriptors", sd->num_entries);
697         sd->total_length += size + sizeof(sd->sizes[0]);
698         insert_sd_node(sd_set, new);
699         return new->security_id;
700 out_free_descr:
701         FREE(descr_copy);
702 out_free_node:
703         FREE(new);
704 out:
705         return -1;
706 }
707 #endif /* WITH_NTFS_3G || __WIN32__ */