Changeset e9f4b59 in mainline for kernel/genarch/src/acpi/madt.c

Timestamp:

2010-06-30T20:29:25Z (14 years ago)

Author:

Martin Decky <martin@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

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:

• kernel/genarch/src/acpi/madt.c (modified) (2 diffs)

kernel/genarch/src/acpi/madt.c

@@ -131 +131 @@
 };
 
-static int madt_cmp(void *a, void *b)
-{
-        uint8_t typea = ((struct madt_apic_header *) a)->type;
-        uint8_t typeb = ((struct madt_apic_header *) b)->type;
+static int madt_cmp(void *a, void *b, void *arg)
+{
+        uint8_t typea = (*((struct madt_apic_header **) a))->type;
+        uint8_t typeb = (*((struct madt_apic_header **) b))->type;
         
         if (typea > typeb)
@@ -208 +208 @@
         
         /* Sort MADT index structure */
-        qsort(madt_entries_index, madt_entries_index_cnt, sizeof(uintptr_t),
-            &madt_cmp);
+        if (!gsort(madt_entries_index, madt_entries_index_cnt,
+            sizeof(struct madt_apic_header *), madt_cmp, NULL))
+                panic("Sorting error.");
         
         /* Parse MADT entries */