Revision d6629859b36d953a4b1369b749f178736911bf10 authored by Doug Ledford on 31 May 2012, 23:26:35 UTC, committed by Linus Torvalds on 01 June 2012, 00:49:31 UTC
The existing implementation of the POSIX message queue send and recv functions is, well, abysmal. Even worse than abysmal. I submitted a patch to increase the maximum POSIX message queue limit to 65536 due to customer needs, however, upon looking over the send/recv implementation, I realized that my customer needs help with that too even if they don't know it. The basic problem is that, given the fairly typical use case scenario for a large queue of queueing lots of messages all at the same priority (I verified with my customer that this is indeed what their app does), the msg_insert routine is basically a frikkin' bubble sort. I mean, whoa, that's *so* middle school. OK, OK, to not slam the original author too much, I'm sure they didn't envision a queue depth of 50,000+ messages. No one would think that moving elements in an array, one at a time, and dereferencing each pointer in that array to check priority of the message being pointed too, again one at a time, for 50,000+ times would be good. So let's assume that, as is typical, the users have found a way to break our code simply by using it in a way we didn't envision. Fair enough. "So, just how broken is it?", you ask. I wondered the same thing, so I wrote an app to let me know. It's my next patch. It gave me some interesting results. Here's what it tested: Interference with other apps - In continuous mode, the app just sits there and hits a message queue forever, while you go do something productive on another terminal using other CPUs. You then measure how long it takes you to do that something productive. Then you restart the app in fake continuous mode, and it sits in a tight loop on a CPU while you repeat your tests. The whole point of this is to keep one CPU tied up (so it can't be used in your other work) but in one case tied up hitting the mqueue code so we can see the effect of walking that 65,528 element array one pointer at a time on the global CPU cache. If it's bad, then it will slow down your app on the other CPUs just by polluting cache mercilessly. In the fake case, it will be in a tight loop, but not polluting cache. Testing the mqueue subsystem directly - Here we just run a number of tests to see how the mqueue subsystem performs under different conditions. A couple conditions are known to be worst case for the old system, and some routines, so this tests all of them. So, on to the results already: Subsystem/Test Old New Time to compile linux kernel (make -j12 on a 6 core CPU) Running mqueue test user 49m10.744s user 45m26.294s sys 5m51.924s sys 4m59.894s total 55m02.668s total 50m26.188s Running fake test user 45m32.686s user 45m18.552s sys 5m12.465s sys 4m56.468s total 50m45.151s total 50m15.020s % slowdown from mqueue cache thrashing ~8% ~.5% Avg time to send/recv (in nanoseconds per message) when queue empty 305/288 349/318 when queue full (65528 messages) constant priority 526589/823 362/314 increasing priority 403105/916 495/445 decreasing priority 73420/594 482/409 random priority 280147/920 546/436 Time to fill/drain queue (65528 messages, in seconds) constant priority 17.37/.12 .13/.12 increasing priority 4.14/.14 .21/.18 decreasing priority 12.93/.13 .21/.18 random priority 8.88/.16 .22/.17 So, I think the results speak for themselves. It's possible this implementation could be improved by cacheing at least one priority level in the node tree (that would bring the queue empty performance more in line with the old implementation), but this works and is *so* much better than what we had, especially for the common case of a single priority in use, that further refinements can be in follow on patches. [akpm@linux-foundation.org: fix typo in comment, remove stray semicolon] [levinsasha928@gmail.com: use correct gfp flags in msg_insert] Signed-off-by: Doug Ledford <dledford@redhat.com> Cc: Stephen Rothwell <sfr@canb.auug.org.au> Cc: Manfred Spraul <manfred@colorfullife.com> Acked-by: KOSAKI Motohiro <kosaki.motohiro@jp.fujitsu.com> Signed-off-by: Sasha Levin <levinsasha928@gmail.com> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
1 parent 50069a5
Makefile.build
# ==========================================================================
# Building
# ==========================================================================
src := $(obj)
PHONY := __build
__build:
# Init all relevant variables used in kbuild files so
# 1) they have correct type
# 2) they do not inherit any value from the environment
obj-y :=
obj-m :=
lib-y :=
lib-m :=
always :=
targets :=
subdir-y :=
subdir-m :=
EXTRA_AFLAGS :=
EXTRA_CFLAGS :=
EXTRA_CPPFLAGS :=
EXTRA_LDFLAGS :=
asflags-y :=
ccflags-y :=
cppflags-y :=
ldflags-y :=
subdir-asflags-y :=
subdir-ccflags-y :=
# Read auto.conf if it exists, otherwise ignore
-include include/config/auto.conf
include scripts/Kbuild.include
# For backward compatibility check that these variables do not change
save-cflags := $(CFLAGS)
# The filename Kbuild has precedence over Makefile
kbuild-dir := $(if $(filter /%,$(src)),$(src),$(srctree)/$(src))
kbuild-file := $(if $(wildcard $(kbuild-dir)/Kbuild),$(kbuild-dir)/Kbuild,$(kbuild-dir)/Makefile)
include $(kbuild-file)
# If the save-* variables changed error out
ifeq ($(KBUILD_NOPEDANTIC),)
ifneq ("$(save-cflags)","$(CFLAGS)")
$(error CFLAGS was changed in "$(kbuild-file)". Fix it to use ccflags-y)
endif
endif
#
# make W=... settings
#
# W=1 - warnings that may be relevant and does not occur too often
# W=2 - warnings that occur quite often but may still be relevant
# W=3 - the more obscure warnings, can most likely be ignored
#
# $(call cc-option, -W...) handles gcc -W.. options which
# are not supported by all versions of the compiler
ifdef KBUILD_ENABLE_EXTRA_GCC_CHECKS
warning- := $(empty)
warning-1 := -Wextra -Wunused -Wno-unused-parameter
warning-1 += -Wmissing-declarations
warning-1 += -Wmissing-format-attribute
warning-1 += -Wmissing-prototypes
warning-1 += -Wold-style-definition
warning-1 += $(call cc-option, -Wmissing-include-dirs)
warning-1 += $(call cc-option, -Wunused-but-set-variable)
warning-1 += $(call cc-disable-warning, missing-field-initializers)
warning-2 := -Waggregate-return
warning-2 += -Wcast-align
warning-2 += -Wdisabled-optimization
warning-2 += -Wnested-externs
warning-2 += -Wshadow
warning-2 += $(call cc-option, -Wlogical-op)
warning-2 += $(call cc-option, -Wmissing-field-initializers)
warning-3 := -Wbad-function-cast
warning-3 += -Wcast-qual
warning-3 += -Wconversion
warning-3 += -Wpacked
warning-3 += -Wpadded
warning-3 += -Wpointer-arith
warning-3 += -Wredundant-decls
warning-3 += -Wswitch-default
warning-3 += $(call cc-option, -Wpacked-bitfield-compat)
warning-3 += $(call cc-option, -Wvla)
warning := $(warning-$(findstring 1, $(KBUILD_ENABLE_EXTRA_GCC_CHECKS)))
warning += $(warning-$(findstring 2, $(KBUILD_ENABLE_EXTRA_GCC_CHECKS)))
warning += $(warning-$(findstring 3, $(KBUILD_ENABLE_EXTRA_GCC_CHECKS)))
ifeq ("$(strip $(warning))","")
$(error W=$(KBUILD_ENABLE_EXTRA_GCC_CHECKS) is unknown)
endif
KBUILD_CFLAGS += $(warning)
endif
include scripts/Makefile.lib
ifdef host-progs
ifneq ($(hostprogs-y),$(host-progs))
$(warning kbuild: $(obj)/Makefile - Usage of host-progs is deprecated. Please replace with hostprogs-y!)
hostprogs-y += $(host-progs)
endif
endif
# Do not include host rules unless needed
ifneq ($(hostprogs-y)$(hostprogs-m),)
include scripts/Makefile.host
endif
ifneq ($(KBUILD_SRC),)
# Create output directory if not already present
_dummy := $(shell [ -d $(obj) ] || mkdir -p $(obj))
# Create directories for object files if directory does not exist
# Needed when obj-y := dir/file.o syntax is used
_dummy := $(foreach d,$(obj-dirs), $(shell [ -d $(d) ] || mkdir -p $(d)))
endif
ifndef obj
$(warning kbuild: Makefile.build is included improperly)
endif
# ===========================================================================
ifneq ($(strip $(lib-y) $(lib-m) $(lib-n) $(lib-)),)
lib-target := $(obj)/lib.a
endif
ifneq ($(strip $(obj-y) $(obj-m) $(obj-n) $(obj-) $(subdir-m) $(lib-target)),)
builtin-target := $(obj)/built-in.o
endif
modorder-target := $(obj)/modules.order
# We keep a list of all modules in $(MODVERDIR)
__build: $(if $(KBUILD_BUILTIN),$(builtin-target) $(lib-target) $(extra-y)) \
$(if $(KBUILD_MODULES),$(obj-m) $(modorder-target)) \
$(subdir-ym) $(always)
@:
# Linus' kernel sanity checking tool
ifneq ($(KBUILD_CHECKSRC),0)
ifeq ($(KBUILD_CHECKSRC),2)
quiet_cmd_force_checksrc = CHECK $<
cmd_force_checksrc = $(CHECK) $(CHECKFLAGS) $(c_flags) $< ;
else
quiet_cmd_checksrc = CHECK $<
cmd_checksrc = $(CHECK) $(CHECKFLAGS) $(c_flags) $< ;
endif
endif
# Do section mismatch analysis for each module/built-in.o
ifdef CONFIG_DEBUG_SECTION_MISMATCH
cmd_secanalysis = ; scripts/mod/modpost $@
endif
# Compile C sources (.c)
# ---------------------------------------------------------------------------
# Default is built-in, unless we know otherwise
modkern_cflags = \
$(if $(part-of-module), \
$(KBUILD_CFLAGS_MODULE) $(CFLAGS_MODULE), \
$(KBUILD_CFLAGS_KERNEL) $(CFLAGS_KERNEL))
quiet_modtag := $(empty) $(empty)
$(real-objs-m) : part-of-module := y
$(real-objs-m:.o=.i) : part-of-module := y
$(real-objs-m:.o=.s) : part-of-module := y
$(real-objs-m:.o=.lst): part-of-module := y
$(real-objs-m) : quiet_modtag := [M]
$(real-objs-m:.o=.i) : quiet_modtag := [M]
$(real-objs-m:.o=.s) : quiet_modtag := [M]
$(real-objs-m:.o=.lst): quiet_modtag := [M]
$(obj-m) : quiet_modtag := [M]
# Default for not multi-part modules
modname = $(basetarget)
$(multi-objs-m) : modname = $(modname-multi)
$(multi-objs-m:.o=.i) : modname = $(modname-multi)
$(multi-objs-m:.o=.s) : modname = $(modname-multi)
$(multi-objs-m:.o=.lst) : modname = $(modname-multi)
$(multi-objs-y) : modname = $(modname-multi)
$(multi-objs-y:.o=.i) : modname = $(modname-multi)
$(multi-objs-y:.o=.s) : modname = $(modname-multi)
$(multi-objs-y:.o=.lst) : modname = $(modname-multi)
quiet_cmd_cc_s_c = CC $(quiet_modtag) $@
cmd_cc_s_c = $(CC) $(c_flags) -fverbose-asm -S -o $@ $<
$(obj)/%.s: $(src)/%.c FORCE
$(call if_changed_dep,cc_s_c)
quiet_cmd_cc_i_c = CPP $(quiet_modtag) $@
cmd_cc_i_c = $(CPP) $(c_flags) -o $@ $<
$(obj)/%.i: $(src)/%.c FORCE
$(call if_changed_dep,cc_i_c)
cmd_gensymtypes = \
$(CPP) -D__GENKSYMS__ $(c_flags) $< | \
$(GENKSYMS) $(if $(1), -T $(2)) -a $(ARCH) \
$(if $(KBUILD_PRESERVE),-p) \
-r $(firstword $(wildcard $(2:.symtypes=.symref) /dev/null))
quiet_cmd_cc_symtypes_c = SYM $(quiet_modtag) $@
cmd_cc_symtypes_c = \
set -e; \
$(call cmd_gensymtypes,true,$@) >/dev/null; \
test -s $@ || rm -f $@
$(obj)/%.symtypes : $(src)/%.c FORCE
$(call cmd,cc_symtypes_c)
# C (.c) files
# The C file is compiled and updated dependency information is generated.
# (See cmd_cc_o_c + relevant part of rule_cc_o_c)
quiet_cmd_cc_o_c = CC $(quiet_modtag) $@
ifndef CONFIG_MODVERSIONS
cmd_cc_o_c = $(CC) $(c_flags) -c -o $@ $<
else
# When module versioning is enabled the following steps are executed:
# o compile a .tmp_<file>.o from <file>.c
# o if .tmp_<file>.o doesn't contain a __ksymtab version, i.e. does
# not export symbols, we just rename .tmp_<file>.o to <file>.o and
# are done.
# o otherwise, we calculate symbol versions using the good old
# genksyms on the preprocessed source and postprocess them in a way
# that they are usable as a linker script
# o generate <file>.o from .tmp_<file>.o using the linker to
# replace the unresolved symbols __crc_exported_symbol with
# the actual value of the checksum generated by genksyms
cmd_cc_o_c = $(CC) $(c_flags) -c -o $(@D)/.tmp_$(@F) $<
cmd_modversions = \
if $(OBJDUMP) -h $(@D)/.tmp_$(@F) | grep -q __ksymtab; then \
$(call cmd_gensymtypes,$(KBUILD_SYMTYPES),$(@:.o=.symtypes)) \
> $(@D)/.tmp_$(@F:.o=.ver); \
\
$(LD) $(LDFLAGS) -r -o $@ $(@D)/.tmp_$(@F) \
-T $(@D)/.tmp_$(@F:.o=.ver); \
rm -f $(@D)/.tmp_$(@F) $(@D)/.tmp_$(@F:.o=.ver); \
else \
mv -f $(@D)/.tmp_$(@F) $@; \
fi;
endif
ifdef CONFIG_FTRACE_MCOUNT_RECORD
ifdef BUILD_C_RECORDMCOUNT
ifeq ("$(origin RECORDMCOUNT_WARN)", "command line")
RECORDMCOUNT_FLAGS = -w
endif
# Due to recursion, we must skip empty.o.
# The empty.o file is created in the make process in order to determine
# the target endianness and word size. It is made before all other C
# files, including recordmcount.
sub_cmd_record_mcount = \
if [ $(@) != "scripts/mod/empty.o" ]; then \
$(objtree)/scripts/recordmcount $(RECORDMCOUNT_FLAGS) "$(@)"; \
fi;
recordmcount_source := $(srctree)/scripts/recordmcount.c \
$(srctree)/scripts/recordmcount.h
else
sub_cmd_record_mcount = set -e ; perl $(srctree)/scripts/recordmcount.pl "$(ARCH)" \
"$(if $(CONFIG_CPU_BIG_ENDIAN),big,little)" \
"$(if $(CONFIG_64BIT),64,32)" \
"$(OBJDUMP)" "$(OBJCOPY)" "$(CC) $(KBUILD_CFLAGS)" \
"$(LD)" "$(NM)" "$(RM)" "$(MV)" \
"$(if $(part-of-module),1,0)" "$(@)";
recordmcount_source := $(srctree)/scripts/recordmcount.pl
endif
cmd_record_mcount = \
if [ "$(findstring -pg,$(_c_flags))" = "-pg" ]; then \
$(sub_cmd_record_mcount) \
fi;
endif
define rule_cc_o_c
$(call echo-cmd,checksrc) $(cmd_checksrc) \
$(call echo-cmd,cc_o_c) $(cmd_cc_o_c); \
$(cmd_modversions) \
$(call echo-cmd,record_mcount) \
$(cmd_record_mcount) \
scripts/basic/fixdep $(depfile) $@ '$(call make-cmd,cc_o_c)' > \
$(dot-target).tmp; \
rm -f $(depfile); \
mv -f $(dot-target).tmp $(dot-target).cmd
endef
# Built-in and composite module parts
$(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
$(call cmd,force_checksrc)
$(call if_changed_rule,cc_o_c)
# Single-part modules are special since we need to mark them in $(MODVERDIR)
$(single-used-m): $(obj)/%.o: $(src)/%.c $(recordmcount_source) FORCE
$(call cmd,force_checksrc)
$(call if_changed_rule,cc_o_c)
@{ echo $(@:.o=.ko); echo $@; } > $(MODVERDIR)/$(@F:.o=.mod)
quiet_cmd_cc_lst_c = MKLST $@
cmd_cc_lst_c = $(CC) $(c_flags) -g -c -o $*.o $< && \
$(CONFIG_SHELL) $(srctree)/scripts/makelst $*.o \
System.map $(OBJDUMP) > $@
$(obj)/%.lst: $(src)/%.c FORCE
$(call if_changed_dep,cc_lst_c)
# Compile assembler sources (.S)
# ---------------------------------------------------------------------------
modkern_aflags := $(KBUILD_AFLAGS_KERNEL) $(AFLAGS_KERNEL)
$(real-objs-m) : modkern_aflags := $(KBUILD_AFLAGS_MODULE) $(AFLAGS_MODULE)
$(real-objs-m:.o=.s): modkern_aflags := $(KBUILD_AFLAGS_MODULE) $(AFLAGS_MODULE)
quiet_cmd_as_s_S = CPP $(quiet_modtag) $@
cmd_as_s_S = $(CPP) $(a_flags) -o $@ $<
$(obj)/%.s: $(src)/%.S FORCE
$(call if_changed_dep,as_s_S)
quiet_cmd_as_o_S = AS $(quiet_modtag) $@
cmd_as_o_S = $(CC) $(a_flags) -c -o $@ $<
$(obj)/%.o: $(src)/%.S FORCE
$(call if_changed_dep,as_o_S)
targets += $(real-objs-y) $(real-objs-m) $(lib-y)
targets += $(extra-y) $(MAKECMDGOALS) $(always)
# Linker scripts preprocessor (.lds.S -> .lds)
# ---------------------------------------------------------------------------
quiet_cmd_cpp_lds_S = LDS $@
cmd_cpp_lds_S = $(CPP) $(cpp_flags) -P -C -U$(ARCH) \
-D__ASSEMBLY__ -DLINKER_SCRIPT -o $@ $<
$(obj)/%.lds: $(src)/%.lds.S FORCE
$(call if_changed_dep,cpp_lds_S)
# Build the compiled-in targets
# ---------------------------------------------------------------------------
# To build objects in subdirs, we need to descend into the directories
$(sort $(subdir-obj-y)): $(subdir-ym) ;
#
# Rule to compile a set of .o files into one .o file
#
ifdef builtin-target
quiet_cmd_link_o_target = LD $@
# If the list of objects to link is empty, just create an empty built-in.o
cmd_link_o_target = $(if $(strip $(obj-y)),\
$(LD) $(ld_flags) -r -o $@ $(filter $(obj-y), $^) \
$(cmd_secanalysis),\
rm -f $@; $(AR) rcs$(KBUILD_ARFLAGS) $@)
$(builtin-target): $(obj-y) FORCE
$(call if_changed,link_o_target)
targets += $(builtin-target)
endif # builtin-target
#
# Rule to create modules.order file
#
# Create commands to either record .ko file or cat modules.order from
# a subdirectory
modorder-cmds = \
$(foreach m, $(modorder), \
$(if $(filter %/modules.order, $m), \
cat $m;, echo kernel/$m;))
$(modorder-target): $(subdir-ym) FORCE
$(Q)(cat /dev/null; $(modorder-cmds)) > $@
#
# Rule to compile a set of .o files into one .a file
#
ifdef lib-target
quiet_cmd_link_l_target = AR $@
cmd_link_l_target = rm -f $@; $(AR) rcs$(KBUILD_ARFLAGS) $@ $(lib-y)
$(lib-target): $(lib-y) FORCE
$(call if_changed,link_l_target)
targets += $(lib-target)
endif
#
# Rule to link composite objects
#
# Composite objects are specified in kbuild makefile as follows:
# <composite-object>-objs := <list of .o files>
# or
# <composite-object>-y := <list of .o files>
link_multi_deps = \
$(filter $(addprefix $(obj)/, \
$($(subst $(obj)/,,$(@:.o=-objs))) \
$($(subst $(obj)/,,$(@:.o=-y)))), $^)
quiet_cmd_link_multi-y = LD $@
cmd_link_multi-y = $(LD) $(ld_flags) -r -o $@ $(link_multi_deps) $(cmd_secanalysis)
quiet_cmd_link_multi-m = LD [M] $@
cmd_link_multi-m = $(cmd_link_multi-y)
# We would rather have a list of rules like
# foo.o: $(foo-objs)
# but that's not so easy, so we rather make all composite objects depend
# on the set of all their parts
$(multi-used-y) : %.o: $(multi-objs-y) FORCE
$(call if_changed,link_multi-y)
$(multi-used-m) : %.o: $(multi-objs-m) FORCE
$(call if_changed,link_multi-m)
@{ echo $(@:.o=.ko); echo $(link_multi_deps); } > $(MODVERDIR)/$(@F:.o=.mod)
targets += $(multi-used-y) $(multi-used-m)
# Descending
# ---------------------------------------------------------------------------
PHONY += $(subdir-ym)
$(subdir-ym):
$(Q)$(MAKE) $(build)=$@
# Add FORCE to the prequisites of a target to force it to be always rebuilt.
# ---------------------------------------------------------------------------
PHONY += FORCE
FORCE:
# Read all saved command lines and dependencies for the $(targets) we
# may be building above, using $(if_changed{,_dep}). As an
# optimization, we don't need to read them if the target does not
# exist, we will rebuild anyway in that case.
targets := $(wildcard $(sort $(targets)))
cmd_files := $(wildcard $(foreach f,$(targets),$(dir $(f)).$(notdir $(f)).cmd))
ifneq ($(cmd_files),)
include $(cmd_files)
endif
# Declare the contents of the .PHONY variable as phony. We keep that
# information in a variable se we can use it in if_changed and friends.
.PHONY: $(PHONY)
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...