From 5a1f6d25647199a4ce6cb41550140c177079b02b Mon Sep 17 00:00:00 2001 From: Jay Krell Date: Wed, 14 Aug 2019 03:22:40 -0700 Subject: [PATCH] Skip degenerate qsort: num < 2, size == 0, base == 0 (mono/mono#16016) Fixes https://github.com/mono/mono/issues/15994 Some is redundant for some qsort implementations. Commit migrated from https://github.com/mono/mono/commit/12de10007cf9a2973452c9cf2df36692808fefb6 --- src/mono/mono/dis/main.c | 6 +++--- src/mono/mono/eglib/glib.h | 11 +++++++++++ src/mono/mono/eglib/gptrarray.c | 2 +- src/mono/mono/metadata/icall-table.c | 2 +- src/mono/mono/metadata/mono-ptr-array.h | 2 +- src/mono/mono/metadata/object.c | 2 +- src/mono/mono/metadata/sgen-bridge.c | 4 ++-- src/mono/mono/metadata/sre-save.c | 16 ++++++++-------- src/mono/mono/metadata/w32handle.c | 2 +- src/mono/mono/mini/aot-compiler.c | 2 +- src/mono/mono/mini/dwarfwriter.c | 2 +- src/mono/mono/profiler/mprof-report.c | 20 ++++++++++---------- src/mono/mono/unit-tests/test-sgen-qsort.c | 2 +- src/mono/mono/utils/mono-os-wait-win32.c | 2 +- 14 files changed, 43 insertions(+), 32 deletions(-) diff --git a/src/mono/mono/dis/main.c b/src/mono/mono/dis/main.c index 417105e..17162f0 100644 --- a/src/mono/mono/dis/main.c +++ b/src/mono/mono/dis/main.c @@ -1782,9 +1782,9 @@ sort_filter_elems (void) for (item = filter_list; item; item = item->next) { ifilter = (ImageFilter *)item->data; - qsort (ifilter->types.elems, ifilter->types.count, sizeof (int), int_cmp); - qsort (ifilter->fields.elems, ifilter->fields.count, sizeof (int), int_cmp); - qsort (ifilter->methods.elems, ifilter->methods.count, sizeof (int), int_cmp); + mono_qsort (ifilter->types.elems, ifilter->types.count, sizeof (int), int_cmp); + mono_qsort (ifilter->fields.elems, ifilter->fields.count, sizeof (int), int_cmp); + mono_qsort (ifilter->methods.elems, ifilter->methods.count, sizeof (int), int_cmp); } } diff --git a/src/mono/mono/eglib/glib.h b/src/mono/mono/eglib/glib.h index c4b54ee..3de7911 100644 --- a/src/mono/mono/eglib/glib.h +++ b/src/mono/mono/eglib/glib.h @@ -1389,6 +1389,17 @@ glong g_utf8_pointer_to_offset (const gchar *str, const gchar *pos); G_END_DECLS +static inline +void +mono_qsort (void* base, size_t num, size_t size, int (*compare)(const void*, const void*)) +{ + g_assert (compare); + g_assert (size); + if (num < 2 || !size || !base) + return; + qsort (base, num, size, compare); +} + // For each allocator; i.e. returning gpointer that needs to be cast. // Macros do not recurse, so naming function and macro the same is ok. // However these are also already macros. diff --git a/src/mono/mono/eglib/gptrarray.c b/src/mono/mono/eglib/gptrarray.c index 8d08729..d18d3e8 100644 --- a/src/mono/mono/eglib/gptrarray.c +++ b/src/mono/mono/eglib/gptrarray.c @@ -214,7 +214,7 @@ void g_ptr_array_sort(GPtrArray *array, GCompareFunc compare) { g_return_if_fail(array != NULL); - qsort(array->pdata, array->len, sizeof(gpointer), compare); + mono_qsort (array->pdata, array->len, sizeof(gpointer), compare); } void diff --git a/src/mono/mono/metadata/icall-table.c b/src/mono/mono/metadata/icall-table.c index 1bffd3f..f019858 100644 --- a/src/mono/mono/metadata/icall-table.c +++ b/src/mono/mono/metadata/icall-table.c @@ -302,7 +302,7 @@ mono_lookup_icall_symbol_internal (gpointer func) // Initialize with identity mapping. One line is easier to step over. for (T i = 0; i < N; ++i) functions_sorted [i] = i; - qsort (functions_sorted, N, sizeof (T), mono_qsort_icall_function_compare_indirect); + mono_qsort (functions_sorted, N, sizeof (T), mono_qsort_icall_function_compare_indirect); gpointer old = mono_atomic_cas_ptr ((gpointer*)&static_functions_sorted, functions_sorted, NULL); if (old) diff --git a/src/mono/mono/metadata/mono-ptr-array.h b/src/mono/mono/metadata/mono-ptr-array.h index 70694ef..b0c6122 100644 --- a/src/mono/mono/metadata/mono-ptr-array.h +++ b/src/mono/mono/metadata/mono-ptr-array.h @@ -60,7 +60,7 @@ typedef struct { } while (0) #define mono_ptr_array_sort(ARRAY, COMPARE_FUNC) do { \ - qsort ((ARRAY).data, (ARRAY).size, sizeof (gpointer), (COMPARE_FUNC)); \ + mono_qsort ((ARRAY).data, (ARRAY).size, sizeof (gpointer), (COMPARE_FUNC)); \ } while (0) #define mono_ptr_array_set(ARRAY, IDX, VALUE) do { \ diff --git a/src/mono/mono/metadata/object.c b/src/mono/mono/metadata/object.c index f959d67..d29c0ed 100644 --- a/src/mono/mono/metadata/object.c +++ b/src/mono/mono/metadata/object.c @@ -1453,7 +1453,7 @@ imt_sort_slot_entries (MonoImtBuilderEntry *entries) { for (current_entry = entries, i = 0; current_entry != NULL; current_entry = current_entry->next, i++) { sorted_array [i] = current_entry; } - qsort (sorted_array, number_of_entries, sizeof (MonoImtBuilderEntry*), compare_imt_builder_entries); + mono_qsort (sorted_array, number_of_entries, sizeof (MonoImtBuilderEntry*), compare_imt_builder_entries); /*for (i = 0; i < number_of_entries; i++) { print_imt_entry (" sorted array:", sorted_array [i], i); diff --git a/src/mono/mono/metadata/sgen-bridge.c b/src/mono/mono/metadata/sgen-bridge.c index 271e360..558a073 100644 --- a/src/mono/mono/metadata/sgen-bridge.c +++ b/src/mono/mono/metadata/sgen-bridge.c @@ -431,8 +431,8 @@ sgen_compare_bridge_processor_results (SgenBridgeProcessor *a, SgenBridgeProcess b_xrefs [i].dst_scc_index = *scc_index_ptr; } - qsort (a_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs); - qsort (b_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs); + mono_qsort (a_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs); + mono_qsort (b_xrefs, a->num_xrefs, sizeof (MonoGCBridgeXRef), compare_xrefs); for (i = 0; i < a->num_xrefs; ++i) { g_assert (a_xrefs [i].src_scc_index == b_xrefs [i].src_scc_index); diff --git a/src/mono/mono/metadata/sre-save.c b/src/mono/mono/metadata/sre-save.c index 0af60e5..1da61c6 100644 --- a/src/mono/mono/metadata/sre-save.c +++ b/src/mono/mono/metadata/sre-save.c @@ -1502,7 +1502,7 @@ build_compressed_metadata (MonoDynamicImage *assembly, MonoError *error) error_init (error); - qsort (assembly->gen_params->pdata, assembly->gen_params->len, sizeof (gpointer), compare_genericparam); + mono_qsort (assembly->gen_params->pdata, assembly->gen_params->len, sizeof (gpointer), compare_genericparam); for (i = 0; i < assembly->gen_params->len; i++) { GenericParamTableEntry *entry = (GenericParamTableEntry *)g_ptr_array_index (assembly->gen_params, i); if (!write_generic_param_entry (assembly, entry, error)) @@ -1642,26 +1642,26 @@ build_compressed_metadata (MonoDynamicImage *assembly, MonoError *error) /* sort the tables that still need sorting */ table = &assembly->tables [MONO_TABLE_CONSTANT]; if (table->rows) - qsort (table->values + MONO_CONSTANT_SIZE, table->rows, sizeof (guint32) * MONO_CONSTANT_SIZE, compare_constants); + mono_qsort (table->values + MONO_CONSTANT_SIZE, table->rows, sizeof (guint32) * MONO_CONSTANT_SIZE, compare_constants); table = &assembly->tables [MONO_TABLE_METHODSEMANTICS]; if (table->rows) - qsort (table->values + MONO_METHOD_SEMA_SIZE, table->rows, sizeof (guint32) * MONO_METHOD_SEMA_SIZE, compare_semantics); + mono_qsort (table->values + MONO_METHOD_SEMA_SIZE, table->rows, sizeof (guint32) * MONO_METHOD_SEMA_SIZE, compare_semantics); table = &assembly->tables [MONO_TABLE_CUSTOMATTRIBUTE]; if (table->rows) - qsort (table->values + MONO_CUSTOM_ATTR_SIZE, table->rows, sizeof (guint32) * MONO_CUSTOM_ATTR_SIZE, compare_custom_attrs); + mono_qsort (table->values + MONO_CUSTOM_ATTR_SIZE, table->rows, sizeof (guint32) * MONO_CUSTOM_ATTR_SIZE, compare_custom_attrs); table = &assembly->tables [MONO_TABLE_FIELDMARSHAL]; if (table->rows) - qsort (table->values + MONO_FIELD_MARSHAL_SIZE, table->rows, sizeof (guint32) * MONO_FIELD_MARSHAL_SIZE, compare_field_marshal); + mono_qsort (table->values + MONO_FIELD_MARSHAL_SIZE, table->rows, sizeof (guint32) * MONO_FIELD_MARSHAL_SIZE, compare_field_marshal); table = &assembly->tables [MONO_TABLE_NESTEDCLASS]; if (table->rows) - qsort (table->values + MONO_NESTED_CLASS_SIZE, table->rows, sizeof (guint32) * MONO_NESTED_CLASS_SIZE, compare_nested); + mono_qsort (table->values + MONO_NESTED_CLASS_SIZE, table->rows, sizeof (guint32) * MONO_NESTED_CLASS_SIZE, compare_nested); /* Section 21.11 DeclSecurity in Partition II doesn't specify this to be sorted by MS implementation requires it */ table = &assembly->tables [MONO_TABLE_DECLSECURITY]; if (table->rows) - qsort (table->values + MONO_DECL_SECURITY_SIZE, table->rows, sizeof (guint32) * MONO_DECL_SECURITY_SIZE, compare_declsecurity_attrs); + mono_qsort (table->values + MONO_DECL_SECURITY_SIZE, table->rows, sizeof (guint32) * MONO_DECL_SECURITY_SIZE, compare_declsecurity_attrs); table = &assembly->tables [MONO_TABLE_INTERFACEIMPL]; if (table->rows) - qsort (table->values + MONO_INTERFACEIMPL_SIZE, table->rows, sizeof (guint32) * MONO_INTERFACEIMPL_SIZE, compare_interface_impl); + mono_qsort (table->values + MONO_INTERFACEIMPL_SIZE, table->rows, sizeof (guint32) * MONO_INTERFACEIMPL_SIZE, compare_interface_impl); /* compress the tables */ for (i = 0; i < MONO_TABLE_NUM; i++){ diff --git a/src/mono/mono/metadata/w32handle.c b/src/mono/mono/metadata/w32handle.c index ac3efe9..c7077aa 100644 --- a/src/mono/mono/metadata/w32handle.c +++ b/src/mono/mono/metadata/w32handle.c @@ -922,7 +922,7 @@ mono_w32handle_has_duplicates (MonoW32Handle *handles [ ], gsize nhandles) MonoW32Handle *sorted [MONO_W32HANDLE_MAXIMUM_WAIT_OBJECTS]; // 64 memcpy (sorted, handles, nhandles * sizeof (handles[0])); - qsort (sorted, nhandles, sizeof (sorted [0]), g_direct_equal); + mono_qsort (sorted, nhandles, sizeof (sorted [0]), g_direct_equal); for (gsize i = 1; i < nhandles; ++i) { MonoW32Handle * const h1 = sorted [i - 1]; MonoW32Handle * const h2 = sorted [i]; diff --git a/src/mono/mono/mini/aot-compiler.c b/src/mono/mono/mini/aot-compiler.c index aaba8b0..0fe5b44 100644 --- a/src/mono/mono/mini/aot-compiler.c +++ b/src/mono/mono/mini/aot-compiler.c @@ -5910,7 +5910,7 @@ compute_line_numbers (MonoMethod *method, int code_size, MonoDebugMethodJitInfo ln_array = g_new0 (MonoDebugLineNumberEntry, debug_info->num_line_numbers); memcpy (ln_array, debug_info->line_numbers, debug_info->num_line_numbers * sizeof (MonoDebugLineNumberEntry)); - qsort (ln_array, debug_info->num_line_numbers, sizeof (MonoDebugLineNumberEntry), (int (*)(const void *, const void *))compare_lne); + mono_qsort (ln_array, debug_info->num_line_numbers, sizeof (MonoDebugLineNumberEntry), (int (*)(const void *, const void *))compare_lne); native_to_il_offset = g_new0 (int, code_size + 1); diff --git a/src/mono/mono/mini/dwarfwriter.c b/src/mono/mono/mini/dwarfwriter.c index 4e91d4b..4f16fa0 100644 --- a/src/mono/mono/mini/dwarfwriter.c +++ b/src/mono/mono/mini/dwarfwriter.c @@ -1519,7 +1519,7 @@ emit_line_number_info (MonoDwarfWriter *w, MonoMethod *method, ln_array = g_new0 (MonoDebugLineNumberEntry, debug_info->num_line_numbers); memcpy (ln_array, debug_info->line_numbers, debug_info->num_line_numbers * sizeof (MonoDebugLineNumberEntry)); - qsort (ln_array, debug_info->num_line_numbers, sizeof (MonoDebugLineNumberEntry), (int (*)(const void *, const void *))compare_lne); + mono_qsort (ln_array, debug_info->num_line_numbers, sizeof (MonoDebugLineNumberEntry), (int (*)(const void *, const void *))compare_lne); native_to_il_offset = g_new0 (int, code_size + 1); diff --git a/src/mono/mono/profiler/mprof-report.c b/src/mono/mono/profiler/mprof-report.c index 8e689f1..48f89ca 100644 --- a/src/mono/mono/profiler/mprof-report.c +++ b/src/mono/mono/profiler/mprof-report.c @@ -1002,7 +1002,7 @@ dump_samples (void) UnmanagedSymbol** cachedus = NULL; if (!num_stat_samples) return; - qsort (usymbols, usymbols_num, sizeof (UnmanagedSymbol*), compare_usymbol_addr); + mono_qsort (usymbols, usymbols_num, sizeof (UnmanagedSymbol*), compare_usymbol_addr); for (i = 0; i < num_stat_samples; ++i) { MethodDesc *m = lookup_method_by_ip (stat_samples [i]); if (m) { @@ -1038,8 +1038,8 @@ dump_samples (void) unmanaged_hits++; } } - qsort (cachedm, count, sizeof (MethodDesc*), compare_method_samples); - qsort (cachedus, ucount, sizeof (UnmanagedSymbol*), compare_usymbol_samples); + mono_qsort (cachedm, count, sizeof (MethodDesc*), compare_method_samples); + mono_qsort (cachedus, ucount, sizeof (UnmanagedSymbol*), compare_usymbol_samples); set_usym_parent (cachedus, ucount); fprintf (outfile, "\nStatistical samples summary\n"); fprintf (outfile, "\tSample type: %s\n", sample_type_name (stat_sample_desc [0])); @@ -1845,7 +1845,7 @@ sort_context_array (TraceDesc* traces) j++; } } - qsort (traces->traces, traces->count, sizeof (CallContext), compare_callc); + mono_qsort (traces->traces, traces->count, sizeof (CallContext), compare_callc); } static void @@ -3421,7 +3421,7 @@ dump_monitors (void) mdesc = mdesc->next; } } - qsort (monitors, num_monitors, sizeof (void*), compare_monitor); + mono_qsort (monitors, num_monitors, sizeof (void*), compare_monitor); fprintf (outfile, "\nMonitor lock summary\n"); for (i = 0; i < num_monitors; ++i) { MonitorDesc *mdesc = monitors [i]; @@ -3505,7 +3505,7 @@ dump_allocations (void) cd = cd->next; } } - qsort (classes, num_classes, sizeof (void*), compare_class); + mono_qsort (classes, num_classes, sizeof (void*), compare_class); for (i = 0; i < num_classes; ++i) { cd = classes [i]; if (!cd->allocs) @@ -3605,7 +3605,7 @@ dump_methods (void) cd = cd->next; } } - qsort (methods, num_methods, sizeof (void*), compare_method); + mono_qsort (methods, num_methods, sizeof (void*), compare_method); for (i = 0; i < num_methods; ++i) { uint64_t msecs; uint64_t smsecs; @@ -3699,7 +3699,7 @@ heap_shot_summary (HeapShot *hs, int hs_num, HeapShot *last_hs) sorted [ccount++] = cd; } hs->sorted = sorted; - qsort (sorted, ccount, sizeof (void*), compare_heap_class); + mono_qsort (sorted, ccount, sizeof (void*), compare_heap_class); fprintf (outfile, "\n\tHeap shot %d at %.3f secs: size: %llu, object count: %llu, class count: %d, roots: %zd\n", hs_num, (hs->timestamp - startup_time)/1000000000.0, @@ -3737,7 +3737,7 @@ heap_shot_summary (HeapShot *hs, int hs_num, HeapShot *last_hs) rev_sorted [k++] = cd->rev_hash [j]; } assert (cd->rev_count == k); - qsort (rev_sorted, cd->rev_count, sizeof (HeapClassRevRef), compare_rev_class); + mono_qsort (rev_sorted, cd->rev_count, sizeof (HeapClassRevRef), compare_rev_class); if (cd->root_references) fprintf (outfile, "\t\t%zd root references (%zd pinning)\n", cd->root_references, cd->pinned_references); dump_rev_claases (rev_sorted, cd->rev_count); @@ -3772,7 +3772,7 @@ dump_heap_shots (void) i = 0; for (hs = heap_shots; hs; hs = hs->next) hs_sorted [i++] = hs; - qsort (hs_sorted, num_heap_shots, sizeof (void*), compare_heap_shots); + mono_qsort (hs_sorted, num_heap_shots, sizeof (void*), compare_heap_shots); for (i = 0; i < num_heap_shots; ++i) { hs = hs_sorted [i]; heap_shot_summary (hs, i, last_hs); diff --git a/src/mono/mono/unit-tests/test-sgen-qsort.c b/src/mono/mono/unit-tests/test-sgen-qsort.c index 93c339f..0633c6e 100644 --- a/src/mono/mono/unit-tests/test-sgen-qsort.c +++ b/src/mono/mono/unit-tests/test-sgen-qsort.c @@ -71,7 +71,7 @@ compare_sorts (void *base, size_t nel, size_t width, int (*compar) (const void*, memcpy (b1, base, len); memcpy (b2, base, len); - qsort (b1, nel, width, compar); + mono_qsort (b1, nel, width, compar); sgen_qsort (b2, nel, width, compar); /* We can't assert that qsort and sgen_qsort produce the same results diff --git a/src/mono/mono/utils/mono-os-wait-win32.c b/src/mono/mono/utils/mono-os-wait-win32.c index a855cd8..4bd9035 100644 --- a/src/mono/mono/utils/mono-os-wait-win32.c +++ b/src/mono/mono/utils/mono-os-wait-win32.c @@ -193,7 +193,7 @@ win32_wait_for_multiple_objects_ex (DWORD count, CONST HANDLE *handles, BOOL wai && GetLastError () == ERROR_INVALID_PARAMETER) { gpointer handles_sorted [MAXIMUM_WAIT_OBJECTS]; // 64 memcpy (handles_sorted, handles, count * sizeof (handles [0])); - qsort (handles_sorted, count, sizeof (handles_sorted [0]), g_direct_equal); + mono_qsort (handles_sorted, count, sizeof (handles_sorted [0]), g_direct_equal); for (DWORD i = 1; i < count; ++i) { if (handles_sorted [i - 1] == handles_sorted [i]) { mono_error_set_duplicate_wait_object (error); -- 2.7.4