Loading...

XML

Word

Printable

Details

Type: Bug
Resolution: Fixed
Priority: Blocker
Fix Version/s: 0.4.0
Component/s: Tools
Labels:
- REGRESSION

Guilty Revision:
59,547

Description

Since r59547 where we introduced a fast way to build ISOs by specifying a list of files, a nasty hidden bug was present in the mis-usage of the hash-table of directories.
This hash-table features a table of buckets (indexed by the hash modulo size of table), each one being a single linked list of directory hash entries. Each directory hash entry consists in the name of the directory, and pointers to parent directory, list of sub-directories contained in this directory (member "child") and a "next" pointer (plus a pointer for a list of files inside this directory).
The problem resides in the meaning of this "next" pointer. After many investigations, it was found that this pointer was misused, both as a pointer for the "next" directory in the list of directories contained in some parent directory, and as a pointer for the "next" directory seen as an entry in the list of hash entries. So that, by looping over this "next" pointer you could either loop over the directories contained in some given parent directory, AND loop also over non-adjacent directories, that were only related by their hash number !!
The bug by itself manifested after when we tried to free the hash table by looping over the directories by following their directory structure (instead of looping over the elements seen as elements of the hash-table). Therefore it appeared that some elements were freed twice or more, and caused strange crashes in CDMAKE.

An example in the following:

dir_hash_create_dir(dir = 'Profiles/All Users/Start Menu/Programs/System Tools' ; norm = 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS')

HASH DISPLAY before creating dir...

dir_hash_entry 0x00CDEAC0 -- '' (0x00001505, 261)

    dir_hash_entry 0x0084D088 -- 'REACTOS' (0x51996c96, 150)

        dir_hash_entry 0x0084D100 -- 'REACTOS\BIN' (0x233d5ceb, 235)

        dir_hash_entry 0x0084D0B0 -- 'REACTOS\SYSTEM32' (0x01e710bc, 188)

            dir_hash_entry 0x0084D0D8 -- 'REACTOS\SYSTEM32\CONFIG' (0xe1a6658e, 398)

    dir_hash_entry 0x0084D060 -- 'LOADER' (0xbee1737c, 892)

    dir_hash_entry 0x00842278 -- 'PROFILES' (0xb5d0d749, 841)

        dir_hash_entry 0x0084D1A0 -- 'PROFILES\ALL USERS' (0x73894690, 656)

            dir_hash_entry 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

                dir_hash_entry 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

                    dir_hash_entry 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

                    dir_hash_entry 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

                    dir_hash_entry 0x0084D2B8 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSORIES' (0xb1999de6, 486)

                    dir_hash_entry 0x0084D290 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSIBILITY' (0x8b4c701a, 26)

                    dir_hash_entry 0x0084D150 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ADMINISTRATIVE TOOLS' (0x2e36c2c7, 711)

            dir_hash_entry 0x0084D1C8 -- 'PROFILES\ALL USERS\DESKTOP' (0x7a8bf026, 38)

        dir_hash_entry 0x00842248 -- 'PROFILES\DEFAULT USER' (0xb7563c49, 73)

            dir_hash_entry 0x0084D128 -- 'PROFILES\DEFAULT USER\MY DOCUMENTS' (0x4e8b78bd, 189)

            dir_hash_entry 0x0084D010 -- 'PROFILES\DEFAULT USER\START MENU' (0x95aff308, 776)

                dir_hash_entry 0x0084D038 -- 'PROFILES\DEFAULT USER\START MENU\PROGRAMS' (0xa992dfcf, 975)

            dir_hash_entry 0x008422E8 -- 'PROFILES\DEFAULT USER\DESKTOP' (0x106b8edf, 735)

dir_hash_create_dir(dir = 'Profiles/All Users/Start Menu/Programs' ; norm = 'PROFILES\ALL USERS\START MENU\PROGRAMS')

HASH DISPLAY before creating dir...

dir_hash_entry 0x00CDEAC0 -- '' (0x00001505, 261)

    dir_hash_entry 0x0084D088 -- 'REACTOS' (0x51996c96, 150)

        dir_hash_entry 0x0084D100 -- 'REACTOS\BIN' (0x233d5ceb, 235)

        dir_hash_entry 0x0084D0B0 -- 'REACTOS\SYSTEM32' (0x01e710bc, 188)

            dir_hash_entry 0x0084D0D8 -- 'REACTOS\SYSTEM32\CONFIG' (0xe1a6658e, 398)

    dir_hash_entry 0x0084D060 -- 'LOADER' (0xbee1737c, 892)

    dir_hash_entry 0x00842278 -- 'PROFILES' (0xb5d0d749, 841)

        dir_hash_entry 0x0084D1A0 -- 'PROFILES\ALL USERS' (0x73894690, 656)

            dir_hash_entry 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

                dir_hash_entry 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

                    dir_hash_entry 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

                    dir_hash_entry 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

                    dir_hash_entry 0x0084D2B8 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSORIES' (0xb1999de6, 486)

                    dir_hash_entry 0x0084D290 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSIBILITY' (0x8b4c701a, 26)

                    dir_hash_entry 0x0084D150 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ADMINISTRATIVE TOOLS' (0x2e36c2c7, 711)

            dir_hash_entry 0x0084D1C8 -- 'PROFILES\ALL USERS\DESKTOP' (0x7a8bf026, 38)

        dir_hash_entry 0x00842248 -- 'PROFILES\DEFAULT USER' (0xb7563c49, 73)

            dir_hash_entry 0x0084D128 -- 'PROFILES\DEFAULT USER\MY DOCUMENTS' (0x4e8b78bd, 189)

            dir_hash_entry 0x0084D010 -- 'PROFILES\DEFAULT USER\START MENU' (0x95aff308, 776)

                dir_hash_entry 0x0084D038 -- 'PROFILES\DEFAULT USER\START MENU\PROGRAMS' (0xa992dfcf, 975)

            dir_hash_entry 0x008422E8 -- 'PROFILES\DEFAULT USER\DESKTOP' (0x106b8edf, 735)

Step 1

parent_de = 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

parent_de->parent = 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

parent_de->child = 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

parent_de->child->next = 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

parent_de->child->next->next = 0x0084D2B8 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSORIES' (0xb1999de6, 486)

parent_de->next = 0x00000000

de = 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

de->next = 0x00000000

dir_hash_entry 0x00CDEAC0 -- '' (0x00001505, 261)

    dir_hash_entry 0x0084D088 -- 'REACTOS' (0x51996c96, 150)

        dir_hash_entry 0x0084D100 -- 'REACTOS\BIN' (0x233d5ceb, 235)

        dir_hash_entry 0x0084D0B0 -- 'REACTOS\SYSTEM32' (0x01e710bc, 188)

            dir_hash_entry 0x0084D0D8 -- 'REACTOS\SYSTEM32\CONFIG' (0xe1a6658e, 398)

    dir_hash_entry 0x0084D060 -- 'LOADER' (0xbee1737c, 892)

    dir_hash_entry 0x00842278 -- 'PROFILES' (0xb5d0d749, 841)

        dir_hash_entry 0x0084D1A0 -- 'PROFILES\ALL USERS' (0x73894690, 656)

            dir_hash_entry 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

                dir_hash_entry 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

                    dir_hash_entry 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

                    dir_hash_entry 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

                    dir_hash_entry 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

                    dir_hash_entry 0x0084D2B8 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSORIES' (0xb1999de6, 486)

                    dir_hash_entry 0x0084D290 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSIBILITY' (0x8b4c701a, 26)

                    dir_hash_entry 0x0084D150 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ADMINISTRATIVE TOOLS' (0x2e36c2c7, 711)

            dir_hash_entry 0x0084D1C8 -- 'PROFILES\ALL USERS\DESKTOP' (0x7a8bf026, 38)

        dir_hash_entry 0x00842248 -- 'PROFILES\DEFAULT USER' (0xb7563c49, 73)

            dir_hash_entry 0x0084D128 -- 'PROFILES\DEFAULT USER\MY DOCUMENTS' (0x4e8b78bd, 189)

            dir_hash_entry 0x0084D010 -- 'PROFILES\DEFAULT USER\START MENU' (0x95aff308, 776)

                dir_hash_entry 0x0084D038 -- 'PROFILES\DEFAULT USER\START MENU\PROGRAMS' (0xa992dfcf, 975)

            dir_hash_entry 0x008422E8 -- 'PROFILES\DEFAULT USER\DESKTOP' (0x106b8edf, 735)

Step 2

parent_de = 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

parent_de->parent = 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

parent_de->child = 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

parent_de->child->next = 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

parent_de->child->next->next = 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

parent_de->next = 0x00000000

de = 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

de->next = 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

Step 3

parent_de = 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

parent_de->parent = 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

parent_de->child = 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

parent_de->child->next = 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

parent_de->child->next->next = 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

parent_de->next = 0x00000000

de = 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

de->next = 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

HASH DISPLAY after creating dir...

dir_hash_entry 0x00CDEAC0 -- '' (0x00001505, 261)

    dir_hash_entry 0x0084D088 -- 'REACTOS' (0x51996c96, 150)

        dir_hash_entry 0x0084D100 -- 'REACTOS\BIN' (0x233d5ceb, 235)

        dir_hash_entry 0x0084D0B0 -- 'REACTOS\SYSTEM32' (0x01e710bc, 188)

            dir_hash_entry 0x0084D0D8 -- 'REACTOS\SYSTEM32\CONFIG' (0xe1a6658e, 398)

    dir_hash_entry 0x0084D060 -- 'LOADER' (0xbee1737c, 892)

    dir_hash_entry 0x00842278 -- 'PROFILES' (0xb5d0d749, 841)

        dir_hash_entry 0x0084D1A0 -- 'PROFILES\ALL USERS' (0x73894690, 656)

            dir_hash_entry 0x0084D218 -- 'PROFILES\ALL USERS\START MENU' (0x8127a2ef, 751)

                dir_hash_entry 0x0084D178 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS' (0x49a86396, 918)

                    dir_hash_entry 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

                    dir_hash_entry 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

                    dir_hash_entry 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

                    dir_hash_entry 0x0084D2B8 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSORIES' (0xb1999de6, 486)

                    dir_hash_entry 0x0084D290 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSIBILITY' (0x8b4c701a, 26)

                    dir_hash_entry 0x0084D150 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ADMINISTRATIVE TOOLS' (0x2e36c2c7, 711)

            dir_hash_entry 0x0084D1C8 -- 'PROFILES\ALL USERS\DESKTOP' (0x7a8bf026, 38)

        dir_hash_entry 0x00842248 -- 'PROFILES\DEFAULT USER' (0xb7563c49, 73)

            dir_hash_entry 0x0084D128 -- 'PROFILES\DEFAULT USER\MY DOCUMENTS' (0x4e8b78bd, 189)

            dir_hash_entry 0x0084D010 -- 'PROFILES\DEFAULT USER\START MENU' (0x95aff308, 776)

                dir_hash_entry 0x0084D038 -- 'PROFILES\DEFAULT USER\START MENU\PROGRAMS' (0xa992dfcf, 975)

            dir_hash_entry 0x008422E8 -- 'PROFILES\DEFAULT USER\DESKTOP' (0x106b8edf, 735)

            dir_hash_entry 0x0084D330 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\SYSTEM TOOLS' (0xb8e34f08, 776)

            dir_hash_entry 0x0084D308 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\GAMES' (0xa38a971f, 799)

            dir_hash_entry 0x0084D2E0 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ENTERTAINMENT' (0xdf0831f0, 496)

            dir_hash_entry 0x0084D2B8 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSORIES' (0xb1999de6, 486)

            dir_hash_entry 0x0084D290 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ACCESSIBILITY' (0x8b4c701a, 26)

            dir_hash_entry 0x0084D150 -- 'PROFILES\ALL USERS\START MENU\PROGRAMS\ADMINISTRATIVE TOOLS' (0x2e36c2c7, 711)

Before "Step 1" the tree structure is correct. We the insert the "Profiles/All Users/Start Menu/Programs/System Tools" directory. It is first correctly inserted into the directory tree (just after "Step 1") but then after "Step 2" and "3" it went inserted after "PROFILES\DEFAULT USER\START MENU" (and all the other directories following it). This happened just because the "System Tools" directory has the same hashcode as the "Start Menu" directory, and was linked to the corresponding bucket's list via the same "next" pointer that is also used for the "next" directory in the tree.

The corresponding code (in dirhash.c) is:

    de = calloc(1, sizeof(*de));

    de->head = NULL;

    de->child = NULL;

    de->parent = parent_de;

    de->normalized_name = strdup(targetnorm);

    de->case_name = strdup(chop_filename(casename));

    de->hashcode = djb_hash(targetnorm);

    printf("Step 1\n");

    DISPLAY_ELEMENT("parent_de =", parent_de);

    DISPLAY_ELEMENT("parent_de->parent =", parent_de->parent);

    DISPLAY_ELEMENT("parent_de->child =", parent_de->child);

    if (parent_de->child) DISPLAY_ELEMENT("parent_de->child->next =", parent_de->child->next);

    if (parent_de->child && parent_de->child->next) DISPLAY_ELEMENT("parent_de->child->next->next =", parent_de->child->next->next);

    DISPLAY_ELEMENT("parent_de->next =", parent_de->next);

    DISPLAY_ELEMENT("de =", de);

    DISPLAY_ELEMENT("de->next =", de->next);

    de->next = parent_de->child;

    parent_de->child = de;

        dir_hash_display(dh);

        printf("\n\n");

    printf("Step 2\n");

    DISPLAY_ELEMENT("parent_de =", parent_de);

    DISPLAY_ELEMENT("parent_de->parent =", parent_de->parent);

    DISPLAY_ELEMENT("parent_de->child =", parent_de->child);

    if (parent_de->child) DISPLAY_ELEMENT("parent_de->child->next =", parent_de->child->next);

    if (parent_de->child && parent_de->child->next) DISPLAY_ELEMENT("parent_de->child->next->next =", parent_de->child->next->next);

    DISPLAY_ELEMENT("parent_de->next =", parent_de->next);

    DISPLAY_ELEMENT("de =", de);

    DISPLAY_ELEMENT("de->next =", de->next);

    ent = &dh->buckets[de->hashcode % NUM_DIR_HASH_BUCKETS];

    while (*ent)

        ent = &(*ent)->next;

    *ent = de;

    printf("Step 3\n");

    DISPLAY_ELEMENT("parent_de =", parent_de);

    DISPLAY_ELEMENT("parent_de->parent =", parent_de->parent);

    DISPLAY_ELEMENT("parent_de->child =", parent_de->child);

    if (parent_de->child) DISPLAY_ELEMENT("parent_de->child->next =", parent_de->child->next);

    if (parent_de->child && parent_de->child->next) DISPLAY_ELEMENT("parent_de->child->next->next =", parent_de->child->next->next);

    DISPLAY_ELEMENT("parent_de->next =", parent_de->next);

    DISPLAY_ELEMENT("de =", de);

    DISPLAY_ELEMENT("de->next =", de->next);

        printf("\nHASH DISPLAY after creating dir...\n");

        dir_hash_display(dh);

        printf("\n\n");

Clearly it's the step using dh->buckets that introduces the bug.

Attachments

Activity

People

Assignee:: hbelusca

Reporter:: hbelusca

Votes:: 0 Vote for this issue

Watchers:: 1 Start watching this issue

Dates

Due:: 2015-01-28

Created:: 2015-01-27 23:48

Updated:: 2015-07-05 11:55

Resolved:: 2015-01-28 20:28