wimlib.net Git - wimlib/blob - 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 empty_sacl_fixup(u8 *descr, u64 *size_p)
 259 {
 260         if (*size_p >= sizeof(SecurityDescriptor)) {
 261                 SecurityDescriptor *sd = (SecurityDescriptor*)descr;
 262                 u32 sacl_offset = le32_to_cpu(sd->sacl_offset);
 263                 if (sacl_offset == *size_p - sizeof(ACL)) {
 264                         sd->sacl_offset = cpu_to_le32(0);
 265                         *size_p -= sizeof(ACL);
 266                 }
 267         }
 268 }
 269
 270 /*
 271  * Reads the security data from the metadata resource.
 272  *
 273  * @metadata_resource:  An array that contains the uncompressed metadata
 274  *                              resource for the WIM file.
 275  * @metadata_resource_len:      The length of @metadata_resource.  It must be at
 276  *                              least 8 bytes.
 277  * @sd_p:       A pointer to a pointer to a wim_security_data structure that
 278  *              will be filled in with a pointer to a new wim_security_data
 279  *              structure on success.
 280  *
 281  * Note: There is no `offset' argument because the security data is located at
 282  * the beginning of the metadata resource.
 283  */
 284 int read_security_data(const u8 metadata_resource[], u64 metadata_resource_len,
 285                        struct wim_security_data **sd_p)
 286 {
 287         struct wim_security_data *sd;
 288         const u8 *p;
 289         int ret;
 290         u64 total_len;
 291
 292         wimlib_assert(metadata_resource_len >= 8);
 293
 294         /*
 295          * Sorry this function is excessively complicated--- I'm just being
 296          * extremely careful about integer overflows.
 297          */
 298
 299         sd = MALLOC(sizeof(struct wim_security_data));
 300         if (!sd) {
 301                 ERROR("Out of memory");
 302                 return WIMLIB_ERR_NOMEM;
 303         }
 304         sd->sizes       = NULL;
 305         sd->descriptors = NULL;
 306         sd->refcnt      = 1;
 307
 308         p = metadata_resource;
 309         p = get_u32(p, &sd->total_length);
 310         p = get_u32(p, (u32*)&sd->num_entries);
 311
 312         /* The security_id field of each dentry is a signed 32-bit integer, so
 313          * the possible indices into the security descriptors table are 0
 314          * through 0x7fffffff.  Which means 0x80000000 security descriptors
 315          * maximum.  Not like you should ever have anywhere close to that many
 316          * security descriptors! */
 317         if (sd->num_entries > 0x80000000) {
 318                 ERROR("Security data has too many entries!");
 319                 goto out_invalid_sd;
 320         }
 321
 322         /* Verify the listed total length of the security data is big enough to
 323          * include the sizes array, verify that the file data is big enough to
 324          * include it as well, then allocate the array of sizes.
 325          *
 326          * Note: The total length of the security data must fit in a 32-bit
 327          * integer, even though each security descriptor size is a 64-bit
 328          * integer.  This is stupid, and we need to be careful not to actually
 329          * let the security descriptor sizes be over 0xffffffff.  */
 330         if ((u64)sd->total_length > metadata_resource_len) {
 331                 ERROR("Security data total length (%u) is bigger than the "
 332                       "metadata resource length (%"PRIu64")",
 333                       sd->total_length, metadata_resource_len);
 334                 goto out_invalid_sd;
 335         }
 336
 337         DEBUG("Reading security data: %u entries, length = %u",
 338               sd->num_entries, sd->total_length);
 339
 340         if (sd->num_entries == 0) {
 341                 /* No security descriptors.  We allow the total_length field to
 342                  * be either 8 (which is correct, since there are always 2
 343                  * 32-bit integers) or 0. */
 344                 if (sd->total_length != 0 && sd->total_length != 8) {
 345                         ERROR("Invalid security data length (%u): expected 0 or 8",
 346                               sd->total_length);
 347                         goto out_invalid_sd;
 348                 }
 349                 sd->total_length = 8;
 350                 goto out_return_sd;
 351         }
 352
 353         u64 sizes_size = (u64)sd->num_entries * sizeof(u64);
 354         u64 size_no_descriptors = 8 + sizes_size;
 355         if (size_no_descriptors > (u64)sd->total_length) {
 356                 ERROR("Security data total length of %u is too short because "
 357                       "there seem to be at least %"PRIu64" bytes of security data",
 358                       sd->total_length, 8 + sizes_size);
 359                 goto out_invalid_sd;
 360         }
 361
 362         sd->sizes = MALLOC(sizes_size);
 363         if (!sd->sizes) {
 364                 ret = WIMLIB_ERR_NOMEM;
 365                 goto out_free_sd;
 366         }
 367
 368         /* Copy the sizes array in from the file data. */
 369         p = get_bytes(p, sizes_size, sd->sizes);
 370         array_le64_to_cpu(sd->sizes, sd->num_entries);
 371
 372         /* Allocate the array of pointers to descriptors, and read them in. */
 373         sd->descriptors = CALLOC(sd->num_entries, sizeof(u8*));
 374         if (!sd->descriptors) {
 375                 ERROR("Out of memory while allocating security "
 376                       "descriptors");
 377                 ret = WIMLIB_ERR_NOMEM;
 378                 goto out_free_sd;
 379         }
 380         total_len = size_no_descriptors;
 381
 382         for (u32 i = 0; i < sd->num_entries; i++) {
 383                 /* Watch out for huge security descriptor sizes that could
 384                  * overflow the total length and wrap it around. */
 385                 if (total_len + sd->sizes[i] < total_len) {
 386                         ERROR("Caught overflow in security descriptor lengths "
 387                               "(current total length = %"PRIu64", security "
 388                               "descriptor size = %"PRIu64")",
 389                               total_len, sd->sizes[i]);
 390                         goto out_invalid_sd;
 391                 }
 392                 total_len += sd->sizes[i];
 393                 /* This check ensures that the descriptor size fits in a 32 bit
 394                  * integer.  Because if it didn't, the total length would come
 395                  * out bigger than sd->total_length, which is a 32 bit integer.
 396                  * */
 397                 if (total_len > (u64)sd->total_length) {
 398                         ERROR("Security data total length of %u is too short "
 399                               "because there seem to be at least %"PRIu64" "
 400                               "bytes of security data",
 401                               sd->total_length, total_len);
 402                         goto out_invalid_sd;
 403                 }
 404                 sd->descriptors[i] = MALLOC(sd->sizes[i]);
 405                 if (!sd->descriptors[i]) {
 406                         ERROR("Out of memory while allocating security "
 407                               "descriptors");
 408                         ret = WIMLIB_ERR_NOMEM;
 409                         goto out_free_sd;
 410                 }
 411                 p = get_bytes(p, sd->sizes[i], sd->descriptors[i]);
 412                 empty_sacl_fixup(sd->descriptors[i], &sd->sizes[i]);
 413         }
 414         wimlib_assert(total_len <= 0xffffffff);
 415         if (((total_len + 7) & ~7) != ((sd->total_length + 7) & ~7)) {
 416                 ERROR("Expected security data total length = %u, but "
 417                       "calculated %u", sd->total_length, (unsigned)total_len);
 418                 goto out_invalid_sd;
 419         }
 420         sd->total_length = total_len;
 421 out_return_sd:
 422         *sd_p = sd;
 423         return 0;
 424 out_invalid_sd:
 425         ret = WIMLIB_ERR_INVALID_SECURITY_DATA;
 426 out_free_sd:
 427         free_security_data(sd);
 428         return ret;
 429 }
 430
 431 /*
 432  * Writes security data to an in-memory buffer.
 433  */
 434 u8 *write_security_data(const struct wim_security_data *sd, u8 *p)
 435 {
 436         DEBUG("Writing security data (total_length = %"PRIu32", num_entries "
 437               "= %"PRIu32")", sd->total_length, sd->num_entries);
 438
 439         u32 aligned_length = (sd->total_length + 7) & ~7;
 440
 441         u8 *orig_p = p;
 442         p = put_u32(p, aligned_length);
 443         p = put_u32(p, sd->num_entries);
 444
 445         for (u32 i = 0; i < sd->num_entries; i++)
 446                 p = put_u64(p, sd->sizes[i]);
 447
 448         for (u32 i = 0; i < sd->num_entries; i++)
 449                 p = put_bytes(p, sd->sizes[i], sd->descriptors[i]);
 450
 451         wimlib_assert(p - orig_p == sd->total_length);
 452         p = put_zeroes(p, aligned_length - sd->total_length);
 453
 454         DEBUG("Successfully wrote security data.");
 455         return p;
 456 }
 457
 458 static void print_acl(const u8 *p, const char *type)
 459 {
 460         const ACL *acl = (const ACL*)p;
 461         u8 revision = acl->revision;
 462         u16 acl_size = le16_to_cpu(acl->acl_size);
 463         u16 ace_count = le16_to_cpu(acl->ace_count);
 464         printf("    [%s ACL]\n", type);
 465         printf("    Revision = %u\n", revision);
 466         printf("    ACL Size = %u\n", acl_size);
 467         printf("    ACE Count = %u\n", ace_count);
 468
 469         p += sizeof(ACL);
 470         for (u16 i = 0; i < ace_count; i++) {
 471                 const ACEHeader *hdr = (const ACEHeader*)p;
 472                 printf("        [ACE]\n");
 473                 printf("        ACE type  = %d\n", hdr->type);
 474                 printf("        ACE flags = 0x%x\n", hdr->flags);
 475                 printf("        ACE size  = %u\n", hdr->size);
 476                 const AccessAllowedACE *aaa = (const AccessAllowedACE*)hdr;
 477                 printf("        ACE mask = %x\n", le32_to_cpu(aaa->mask));
 478                 printf("        SID start = %u\n", le32_to_cpu(aaa->sid_start));
 479                 p += hdr->size;
 480         }
 481         putchar('\n');
 482 }
 483
 484 static void print_sid(const u8 *p, const char *type)
 485 {
 486         const SID *sid = (const SID*)p;
 487         printf("    [%s SID]\n", type);
 488         printf("    Revision = %u\n", sid->revision);
 489         printf("    Subauthority count = %u\n", sid->sub_authority_count);
 490         printf("    Identifier authority = ");
 491         print_byte_field(sid->identifier_authority,
 492                          sizeof(sid->identifier_authority));
 493         putchar('\n');
 494         for (u8 i = 0; i < sid->sub_authority_count; i++)
 495                 printf("    Subauthority %u = %u\n",
 496                        i, le32_to_cpu(sid->sub_authority[i]));
 497         putchar('\n');
 498 }
 499
 500 static void print_security_descriptor(const u8 *p, u64 size)
 501 {
 502         const SecurityDescriptor *sd = (const SecurityDescriptor*)p;
 503         u8 revision      = sd->revision;
 504         u16 control      = le16_to_cpu(sd->security_descriptor_control);
 505         u32 owner_offset = le32_to_cpu(sd->owner_offset);
 506         u32 group_offset = le32_to_cpu(sd->group_offset);
 507         u32 sacl_offset  = le32_to_cpu(sd->sacl_offset);
 508         u32 dacl_offset  = le32_to_cpu(sd->dacl_offset);
 509         printf("Revision = %u\n", revision);
 510         printf("Security Descriptor Control = %#x\n", control);
 511         printf("Owner offset = %u\n", owner_offset);
 512         printf("Group offset = %u\n", group_offset);
 513         printf("System ACL offset = %u\n", sacl_offset);
 514         printf("Discretionary ACL offset = %u\n", dacl_offset);
 515
 516         if (sd->owner_offset != 0)
 517                 print_sid(p + owner_offset, "Owner");
 518         if (sd->group_offset != 0)
 519                 print_sid(p + group_offset, "Group");
 520         if (sd->sacl_offset != 0)
 521                 print_acl(p + sacl_offset, "System");
 522         if (sd->dacl_offset != 0)
 523                 print_acl(p + dacl_offset, "Discretionary");
 524 }
 525
 526 /*
 527  * Prints the security data for a WIM file.
 528  */
 529 void print_security_data(const struct wim_security_data *sd)
 530 {
 531         wimlib_assert(sd != NULL);
 532
 533         puts("[SECURITY DATA]");
 534         printf("Length            = %"PRIu32" bytes\n", sd->total_length);
 535         printf("Number of Entries = %"PRIu32"\n", sd->num_entries);
 536
 537         for (u32 i = 0; i < sd->num_entries; i++) {
 538                 printf("[SecurityDescriptor %"PRIu32", length = %"PRIu64"]\n",
 539                        i, sd->sizes[i]);
 540                 print_security_descriptor(sd->descriptors[i], sd->sizes[i]);
 541                 putchar('\n');
 542         }
 543         putchar('\n');
 544 }
 545
 546 void free_security_data(struct wim_security_data *sd)
 547 {
 548         if (sd) {
 549                 wimlib_assert(sd->refcnt != 0);
 550                 if (--sd->refcnt == 0) {
 551                         u8 **descriptors = sd->descriptors;
 552                         u32 num_entries  = sd->num_entries;
 553                         if (descriptors)
 554                                 while (num_entries--)
 555                                         FREE(*descriptors++);
 556                         FREE(sd->sizes);
 557                         FREE(sd->descriptors);
 558                         FREE(sd);
 559                 }
 560         }
 561 }
 562
 563 #if defined(WITH_NTFS_3G) || defined(__CYGWIN__) || defined(__WIN32__)
 564 struct sd_node {
 565         int security_id;
 566         u8 hash[SHA1_HASH_SIZE];
 567         struct rb_node rb_node;
 568 };
 569
 570 static void free_sd_tree(struct rb_node *node)
 571 {
 572         if (node) {
 573                 free_sd_tree(node->rb_left);
 574                 free_sd_tree(node->rb_right);
 575                 FREE(container_of(node, struct sd_node, rb_node));
 576         }
 577 }
 578
 579 /* Frees a security descriptor index set. */
 580 void destroy_sd_set(struct sd_set *sd_set)
 581 {
 582         free_sd_tree(sd_set->rb_root.rb_node);
 583 }
 584
 585 /* Inserts a a new node into the security descriptor index tree. */
 586 static void insert_sd_node(struct sd_set *set, struct sd_node *new)
 587 {
 588         struct rb_root *root = &set->rb_root;
 589         struct rb_node **p = &(root->rb_node);
 590         struct rb_node *rb_parent = NULL;
 591
 592         while (*p) {
 593                 struct sd_node *this = container_of(*p, struct sd_node, rb_node);
 594                 int cmp = hashes_cmp(new->hash, this->hash);
 595
 596                 rb_parent = *p;
 597                 if (cmp < 0)
 598                         p = &((*p)->rb_left);
 599                 else if (cmp > 0)
 600                         p = &((*p)->rb_right);
 601                 else
 602                         wimlib_assert(0); /* Duplicate SHA1 message digest */
 603         }
 604         rb_link_node(&new->rb_node, rb_parent, p);
 605         rb_insert_color(&new->rb_node, root);
 606 }
 607
 608 /* Returns the index of the security descriptor having a SHA1 message digest of
 609  * @hash.  If not found, return -1. */
 610 int lookup_sd(struct sd_set *set, const u8 hash[SHA1_HASH_SIZE])
 611 {
 612         struct rb_node *node = set->rb_root.rb_node;
 613
 614         while (node) {
 615                 struct sd_node *sd_node = container_of(node, struct sd_node, rb_node);
 616                 int cmp = hashes_cmp(hash, sd_node->hash);
 617                 if (cmp < 0)
 618                         node = node->rb_left;
 619                 else if (cmp > 0)
 620                         node = node->rb_right;
 621                 else
 622                         return sd_node->security_id;
 623         }
 624         return -1;
 625 }
 626
 627 /*
 628  * Adds a security descriptor to the indexed security descriptor set as well as
 629  * the corresponding `struct wim_security_data', and returns the new security
 630  * ID; or, if there is an existing security descriptor that is the same, return
 631  * the security ID for it.  If a new security descriptor cannot be allocated,
 632  * return -1.
 633  */
 634 int sd_set_add_sd(struct sd_set *sd_set, const char descriptor[],
 635                   size_t size)
 636 {
 637         u8 hash[SHA1_HASH_SIZE];
 638         int security_id;
 639         struct sd_node *new;
 640         u8 **descriptors;
 641         u64 *sizes;
 642         u8 *descr_copy;
 643         struct wim_security_data *sd;
 644
 645         sha1_buffer((const u8*)descriptor, size, hash);
 646
 647         security_id = lookup_sd(sd_set, hash);
 648         if (security_id >= 0) /* Identical descriptor already exists */
 649                 return security_id;
 650
 651         /* Need to add a new security descriptor */
 652         new = MALLOC(sizeof(*new));
 653         if (!new)
 654                 goto out;
 655         descr_copy = MALLOC(size);
 656         if (!descr_copy)
 657                 goto out_free_node;
 658
 659         sd = sd_set->sd;
 660
 661         memcpy(descr_copy, descriptor, size);
 662         new->security_id = sd->num_entries;
 663         copy_hash(new->hash, hash);
 664
 665         descriptors = REALLOC(sd->descriptors,
 666                               (sd->num_entries + 1) * sizeof(sd->descriptors[0]));
 667         if (!descriptors)
 668                 goto out_free_descr;
 669         sd->descriptors = descriptors;
 670         sizes = REALLOC(sd->sizes,
 671                         (sd->num_entries + 1) * sizeof(sd->sizes[0]));
 672         if (!sizes)
 673                 goto out_free_descr;
 674         sd->sizes = sizes;
 675         sd->descriptors[sd->num_entries] = descr_copy;
 676         sd->sizes[sd->num_entries] = size;
 677         sd->num_entries++;
 678         DEBUG("There are now %d security descriptors", sd->num_entries);
 679         sd->total_length += size + sizeof(sd->sizes[0]);
 680         insert_sd_node(sd_set, new);
 681         return new->security_id;
 682 out_free_descr:
 683         FREE(descr_copy);
 684 out_free_node:
 685         FREE(new);
 686 out:
 687         return -1;
 688 }
 689 #endif /* WITH_NTFS_3G || __CYGWIN__ || __WIN32__ */