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