02 Nov, 2017
1 commit
-
Many source files in the tree are missing licensing information, which
makes it harder for compliance tools to determine the correct license.By default all files without license information are under the default
license of the kernel, which is GPL version 2.Update the files which contain no license information with the 'GPL-2.0'
SPDX license identifier. The SPDX identifier is a legally binding
shorthand, which can be used instead of the full boiler plate text.This patch is based on work done by Thomas Gleixner and Kate Stewart and
Philippe Ombredanne.How this work was done:
Patches were generated and checked against linux-4.14-rc6 for a subset of
the use cases:
- file had no licensing information it it.
- file was a */uapi/* one with no licensing information in it,
- file was a */uapi/* one with existing licensing information,Further patches will be generated in subsequent months to fix up cases
where non-standard license headers were used, and references to license
had to be inferred by heuristics based on keywords.The analysis to determine which SPDX License Identifier to be applied to
a file was done in a spreadsheet of side by side results from of the
output of two independent scanners (ScanCode & Windriver) producing SPDX
tag:value files created by Philippe Ombredanne. Philippe prepared the
base worksheet, and did an initial spot review of a few 1000 files.The 4.13 kernel was the starting point of the analysis with 60,537 files
assessed. Kate Stewart did a file by file comparison of the scanner
results in the spreadsheet to determine which SPDX license identifier(s)
to be applied to the file. She confirmed any determination that was not
immediately clear with lawyers working with the Linux Foundation.Criteria used to select files for SPDX license identifier tagging was:
- Files considered eligible had to be source code files.
- Make and config files were included as candidates if they contained >5
lines of source
- File already had some variant of a license header in it (even if
Reviewed-by: Philippe Ombredanne
Reviewed-by: Thomas Gleixner
Signed-off-by: Greg Kroah-Hartman
25 Feb, 2017
1 commit
-
Along with the addition made to Kconfig.debug, the prior existing but
permanently disabled test function has been slightly refactored.Patch has been tested using QEMU 2.1.2 with a .config obtained through
'make defconfig' (x86_64) and manually enabling the option.[arnd@arndb.de: move sort self-test into a separate file]
Link: http://lkml.kernel.org/r/20170112110657.3123790-1-arnd@arndb.de
Link: http://lkml.kernel.org/r/HE1PR09MB0394B0418D504DCD27167D4FD49B0@HE1PR09MB0394.eurprd09.prod.outlook.com
Signed-off-by: Kostenzer Felix
Signed-off-by: Arnd Bergmann
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
26 Jun, 2015
1 commit
-
In case the call side is not providing a swap function, we either use a
32 bit or a generic swap function. When swapping around pointers on 64
bit architectures falling back to use the generic swap function seems
like an unnecessary waste.There at least 9 users ('sort' is of difficult to grep for) of sort()
and all of them use the sort function without a customized swap
function. Furthermore, they are all using pointers to swap around:arch/x86/kernel/e820.c:sanitize_e820_map()
arch/x86/mm/extable.c:sort_extable()
drivers/acpi/fan.c:acpi_fan_get_fps()
fs/btrfs/super.c:btrfs_descending_sort_devices()
fs/xfs/libxfs/xfs_dir2_block.c:xfs_dir2_sf_to_block()
kernel/range.c:clean_sort_range()
mm/memcontrol.c:__mem_cgroup_usage_register_event()
sound/pci/hda/hda_auto_parser.c:snd_hda_parse_pin_defcfg()
sound/pci/hda/hda_auto_parser.c:sort_pins_by_sequence()Obviously, we could improve the swap for other sizes as well
but this is overkill at this point.A simple test shows sorting a 400 element array (try to stay in one
page) with either with u32_swap() or u64_swap() show that the theory
actually works. This test was done on a x86_64 (Intel Xeon E5-4610)
machine.- swap_32:
NumSamples = 100; Min = 48.00; Max = 49.00
Mean = 48.320000; Variance = 0.217600; SD = 0.466476; Median 48.000000
each * represents a count of 1
48.0000 - 48.1000 [ 68]: ********************************************************************
48.1000 - 48.2000 [ 0]:
48.2000 - 48.3000 [ 0]:
48.3000 - 48.4000 [ 0]:
48.4000 - 48.5000 [ 0]:
48.5000 - 48.6000 [ 0]:
48.6000 - 48.7000 [ 0]:
48.7000 - 48.8000 [ 0]:
48.8000 - 48.9000 [ 0]:
48.9000 - 49.0000 [ 32]: ********************************- swap_64:
NumSamples = 100; Min = 44.00; Max = 63.00
Mean = 48.250000; Variance = 18.687500; SD = 4.322904; Median 47.000000
each * represents a count of 1
44.0000 - 45.9000 [ 15]: ***************
45.9000 - 47.8000 [ 37]: *************************************
47.8000 - 49.7000 [ 39]: ***************************************
49.7000 - 51.6000 [ 0]:
51.6000 - 53.5000 [ 0]:
53.5000 - 55.4000 [ 0]:
55.4000 - 57.3000 [ 0]:
57.3000 - 59.2000 [ 1]: *
59.2000 - 61.1000 [ 3]: ***
61.1000 - 63.0000 [ 5]: *****- swap_72:
NumSamples = 100; Min = 53.00; Max = 71.00
Mean = 55.070000; Variance = 21.565100; SD = 4.643824; Median 53.000000
each * represents a count of 1
53.0000 - 54.8000 [ 73]: *************************************************************************
54.8000 - 56.6000 [ 9]: *********
56.6000 - 58.4000 [ 9]: *********
58.4000 - 60.2000 [ 0]:
60.2000 - 62.0000 [ 0]:
62.0000 - 63.8000 [ 0]:
63.8000 - 65.6000 [ 0]:
65.6000 - 67.4000 [ 1]: *
67.4000 - 69.2000 [ 4]: ****
69.2000 - 71.0000 [ 4]: ****- test program:
static int cmp_32(const void *a, const void *b)
{
u32 l = *(u32 *)a;
u32 r = *(u32 *)b;if (l < r)
return -1;
if (l > r)
return 1;
return 0;
}static int cmp_64(const void *a, const void *b)
{
u64 l = *(u64 *)a;
u64 r = *(u64 *)b;if (l < r)
return -1;
if (l > r)
return 1;
return 0;
}static int cmp_72(const void *a, const void *b)
{
u32 l = get_unaligned((u32 *) a);
u32 r = get_unaligned((u32 *) b);if (l < r)
return -1;
if (l > r)
return 1;
return 0;
}static void init_array32(void *array)
{
u32 *a = array;
int i;a[0] = 3821;
for (i = 1; i < ARRAY_ELEMENTS; i++)
a[i] = next_pseudo_random32(a[i-1]);
}static void init_array64(void *array)
{
u64 *a = array;
int i;a[0] = 3821;
for (i = 1; i < ARRAY_ELEMENTS; i++)
a[i] = next_pseudo_random32(a[i-1]);
}static void init_array72(void *array)
{
char *p;
u32 v;
int i;v = 3821;
for (i = 0; i < ARRAY_ELEMENTS; i++) {
p = (char *)array + (i * 9);
put_unaligned(v, (u32*) p);
v = next_pseudo_random32(v);
}
}static void sort_test(void (*init)(void *array),
int (*cmp) (const void *, const void *),
void *array, size_t size)
{
ktime_t start, stop;
int i;for (i = 0; i < 10000; i++) {
init(array);local_irq_disable();
start = ktime_get();sort(array, ARRAY_ELEMENTS, size, cmp, NULL);
stop = ktime_get();
local_irq_enable();if (i > 10000 - 101)
pr_info("%lld\n", ktime_to_us(ktime_sub(stop, start)));
}
}static void *create_array(size_t size)
{
void *array;array = kmalloc(ARRAY_ELEMENTS * size, GFP_KERNEL);
if (!array)
return NULL;return array;
}static int perform_test(size_t size)
{
void *array;array = create_array(size);
if (!array)
return -ENOMEM;pr_info("test element size %d bytes\n", (int)size);
switch (size) {
case 4:
sort_test(init_array32, cmp_32, array, size);
break;
case 8:
sort_test(init_array64, cmp_64, array, size);
break;
case 9:
sort_test(init_array72, cmp_72, array, size);
break;
}
kfree(array);return 0;
}static int __init sort_tests_init(void)
{
int err;err = perform_test(sizeof(u32));
if (err)
return err;err = perform_test(sizeof(u64));
if (err)
return err;err = perform_test(sizeof(u64)+1);
if (err)
return err;return 0;
}static void __exit sort_tests_exit(void)
{
}module_init(sort_tests_init);
module_exit(sort_tests_exit);MODULE_LICENSE("GPL v2");
MODULE_AUTHOR("Daniel Wagner");
MODULE_DESCRIPTION("sort perfomance tests");Signed-off-by: Daniel Wagner
Cc: Rasmus Villemoes
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
13 Feb, 2015
2 commits
-
The sort function and its helpers don't do memory allocation, so the
slab.h include is redundant. Move it inside the #if 0 protecting the
self-test, similar to how it is done in lib/list_sort.c. This removes
over 450 lines from the generated dependency file.Signed-off-by: Rasmus Villemoes
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds -
sort.c doesn't use facilities from kernel.h, but does use some types
defined in linux/types.h. Include the latter directly instead of relying
on some other header doing it. Similarly, include linux/export.h directly
instead of through module.h. This removes 80 lines from the dependency
file .sort.o.cmd.Signed-off-by: Rasmus Villemoes
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
09 Jan, 2009
1 commit
-
This is to avoid name clashes for the introduction of a global swap()
macro.Signed-off-by: Wu Fengguang
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
17 Oct, 2007
1 commit
-
Hello, I fixed and tested a small bug in lib/sort.c file, heap sort
function.The fix avoids unnecessary swap of contents when i is 0 (saves few loads
and stores), which happens every time sort function is called. I felt the
fix is worth bringing it to your attention given the importance and
frequent use of the sort function.Acked-by: Matt Mackall
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
12 Feb, 2007
1 commit
-
A variety of (mostly) innocuous fixes to the embedded kernel-doc content in
source files, including:* make multi-line initial descriptions single line
* denote some function names, constants and structs as such
* change erroneous opening '/*' to '/**' in a few places
* reword some text for claritySigned-off-by: Robert P. J. Day
Cc: "Randy.Dunlap"
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
03 Oct, 2006
1 commit
-
It is a non-standard heap-sort algorithm implementation because the index
of child node is wrong . The sort function still outputs right result, but
the performance is O( n * ( log(n) + 1 ) ) , about 10% ~ 20% worse than
standard algorithm.Signed-off-by: keios
Acked-by: Matt Mackall
Acked-by: Zou Nan hai
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
31 Oct, 2005
1 commit
-
I recently picked up my older work to remove unnecessary #includes of
sched.h, starting from a patch by Dave Jones to not include sched.h
from module.h. This reduces the number of indirect includes of sched.h
by ~300. Another ~400 pointless direct includes can be removed after
this disentangling (patch to follow later).
However, quite a few indirect includes need to be fixed up for this.In order to feed the patches through -mm with as little disturbance as
possible, I've split out the fixes I accumulated up to now (complete for
i386 and x86_64, more archs to follow later) and post them before the real
patch. This way this large part of the patch is kept simple with only
adding #includes, and all hunks are independent of each other. So if any
hunk rejects or gets in the way of other patches, just drop it. My scripts
will pick it up again in the next round.Signed-off-by: Tim Schmielau
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
11 Sep, 2005
1 commit
-
This patch contains the following small cleanups:
- make two needlessly global functions static
- every file should #include the header files containing the prototypes
of it's global functionsSigned-off-by: Adrian Bunk
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
06 May, 2005
1 commit
-
The regression test in lib/sort.c is currently worthless because the array
that is generated for sorting will be all zeros. This patch fixes things
so that the array that is generated will contain unsorted integers (that
are not all identical) as was probably intended.Signed-off-by Daniel Dickman
Signed-off-by: Domen Puncer
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
17 Apr, 2005
1 commit
-
Initial git repository build. I'm not bothering with the full history,
even though we have it. We can create a separate "historical" git
archive of that later if we want to, and in the meantime it's about
3.2GB when imported into git - space that would just make the early
git days unnecessarily complicated, when we don't have a lot of good
infrastructure for it.Let it rip!
