Fork us on GitHub Follow us on Facebook Follow us on Twitter

Changeset e9f4b59 in mainline


Ignore:
Timestamp:
2010-06-30T20:29:25Z (12 years ago)
Author:
Martin Decky <martin@…>
Branches:
lfn, master, serial
Children:
50f4b95
Parents:
4babe62
Message:

Fix two blatant bugs which were present in the MADT parsing code for ages:

  • In madt_cmp() there was a pair of extra dereferences missing, the function was compairing total nonsense.
  • Quicksort is an unstable sorting algorithm. Using it on sorting entries using a non-unique key (such as the MADT APIC Header type) could lead to a change in the relative order of the entries within the same type, thus failing to bind CPU IDs with the corresponding Local APIC IDs. Use gnome sort which is a stable sorting algorithm (it is not particulary efficient, but the MADT entries are usually sorted according to the header type, and gnome sort can detect sorted lists).
File:
1 edited

Legend:

Unmodified
Added
Removed
  • kernel/genarch/src/acpi/madt.c

    r4babe62 re9f4b59  
    131131};
    132132
    133 static int madt_cmp(void *a, void *b)
    134 {
    135         uint8_t typea = ((struct madt_apic_header *) a)->type;
    136         uint8_t typeb = ((struct madt_apic_header *) b)->type;
     133static int madt_cmp(void *a, void *b, void *arg)
     134{
     135        uint8_t typea = (*((struct madt_apic_header **) a))->type;
     136        uint8_t typeb = (*((struct madt_apic_header **) b))->type;
    137137       
    138138        if (typea > typeb)
     
    208208       
    209209        /* Sort MADT index structure */
    210         qsort(madt_entries_index, madt_entries_index_cnt, sizeof(uintptr_t),
    211             &madt_cmp);
     210        if (!gsort(madt_entries_index, madt_entries_index_cnt,
     211            sizeof(struct madt_apic_header *), madt_cmp, NULL))
     212                panic("Sorting error.");
    212213       
    213214        /* Parse MADT entries */
Note: See TracChangeset for help on using the changeset viewer.