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
# Makefile for the different targets used to generate full packages of a kernel
# It uses the generic clean infrastructure of kbuild
# RPM target
# ---------------------------------------------------------------------------
# The rpm target generates two rpm files:
# /usr/src/packages/SRPMS/kernel-2.6.7rc2-1.src.rpm
# /usr/src/packages/RPMS/i386/kernel-2.6.7rc2-1.<arch>.rpm
# The src.rpm files includes all source for the kernel being built
# The <arch>.rpm includes kernel configuration, modules etc.
#
# Process to create the rpm files
# a) clean the kernel
# b) Generate .spec file
# c) Build a tar ball, using symlink to make kernel version
# first entry in the path
# d) and pack the result to a tar.gz file
# e) generate the rpm files, based on kernel.spec
# - Use /. to avoid tar packing just the symlink
# Note that the rpm-pkg target cannot be used with KBUILD_OUTPUT,
# but the binrpm-pkg target can; for some reason O= gets ignored.
# Do we have rpmbuild, otherwise fall back to the older rpm
RPM := $(shell if [ -x "/usr/bin/rpmbuild" ]; then echo rpmbuild; \
else echo rpm; fi)
# Remove hyphens since they have special meaning in RPM filenames
KERNELPATH := kernel-$(subst -,_,$(KERNELRELEASE))
MKSPEC := $(srctree)/scripts/package/mkspec
PREV := set -e; cd -P ..;
# rpm-pkg
# ---------------------------------------------------------------------------
$(objtree)/kernel.spec: $(MKSPEC) $(srctree)/Makefile
$(CONFIG_SHELL) $(MKSPEC) > $@
rpm-pkg rpm: $(objtree)/kernel.spec FORCE
@if test -n "$(KBUILD_OUTPUT)"; then \
echo "Building source + binary RPM is not possible outside the"; \
echo "kernel source tree. Don't set KBUILD_OUTPUT, or use the"; \
echo "binrpm-pkg target instead."; \
false; \
fi
$(MAKE) clean
$(PREV) ln -sf $(srctree) $(KERNELPATH)
$(CONFIG_SHELL) $(srctree)/scripts/setlocalversion --save-scmversion
$(PREV) tar -cz $(RCS_TAR_IGNORE) -f $(KERNELPATH).tar.gz $(KERNELPATH)/.
$(PREV) rm $(KERNELPATH)
rm -f $(objtree)/.scmversion
set -e; \
$(CONFIG_SHELL) $(srctree)/scripts/mkversion > $(objtree)/.tmp_version
set -e; \
mv -f $(objtree)/.tmp_version $(objtree)/.version
$(RPM) $(RPMOPTS) --target $(UTS_MACHINE) -ta ../$(KERNELPATH).tar.gz
rm ../$(KERNELPATH).tar.gz
clean-files := $(objtree)/kernel.spec
# binrpm-pkg
# ---------------------------------------------------------------------------
$(objtree)/binkernel.spec: $(MKSPEC) $(srctree)/Makefile
$(CONFIG_SHELL) $(MKSPEC) prebuilt > $@
binrpm-pkg: $(objtree)/binkernel.spec FORCE
$(MAKE) KBUILD_SRC=
set -e; \
$(CONFIG_SHELL) $(srctree)/scripts/mkversion > $(objtree)/.tmp_version
set -e; \
mv -f $(objtree)/.tmp_version $(objtree)/.version
$(RPM) $(RPMOPTS) --define "_builddir $(objtree)" --target \
$(UTS_MACHINE) -bb $<
clean-files += $(objtree)/binkernel.spec
# Deb target
# ---------------------------------------------------------------------------
quiet_cmd_builddeb = BUILDDEB
cmd_builddeb = set -e; \
test `id -u` = 0 || \
test -n "$(KBUILD_PKG_ROOTCMD)" || { \
which fakeroot >/dev/null 2>&1 && \
KBUILD_PKG_ROOTCMD="fakeroot -u"; \
} || { \
echo; \
echo "builddeb must be run as root (or using fakeroot)."; \
echo "KBUILD_PKG_ROOTCMD is unset and fakeroot not found."; \
echo "Try setting KBUILD_PKG_ROOTCMD to a command to acquire"; \
echo "root privileges (e.g., 'fakeroot -u' or 'sudo')."; \
false; \
} && \
\
$$KBUILD_PKG_ROOTCMD $(CONFIG_SHELL) \
$(srctree)/scripts/package/builddeb
deb-pkg: FORCE
$(MAKE) KBUILD_SRC=
$(call cmd,builddeb)
clean-dirs += $(objtree)/debian/
# tarball targets
# ---------------------------------------------------------------------------
tar%pkg: FORCE
$(MAKE) KBUILD_SRC=
$(CONFIG_SHELL) $(srctree)/scripts/package/buildtar $@
clean-dirs += $(objtree)/tar-install/
# perf-pkg - generate a source tarball with perf source
# ---------------------------------------------------------------------------
perf-tar=perf-$(KERNELVERSION)
quiet_cmd_perf_tar = TAR
cmd_perf_tar = \
git --git-dir=$(srctree)/.git archive --prefix=$(perf-tar)/ \
HEAD^{tree} $$(cd $(srctree); \
echo $$(cat $(srctree)/tools/perf/MANIFEST)) \
-o $(perf-tar).tar; \
mkdir -p $(perf-tar); \
git --git-dir=$(srctree)/.git rev-parse HEAD > $(perf-tar)/HEAD; \
tar rf $(perf-tar).tar $(perf-tar)/HEAD; \
rm -r $(perf-tar); \
$(if $(findstring tar-src,$@),, \
$(if $(findstring bz2,$@),bzip2, \
$(if $(findstring gz,$@),gzip, \
$(if $(findstring xz,$@),xz, \
$(error unknown target $@)))) \
-f -9 $(perf-tar).tar)
perf-%pkg: FORCE
$(call cmd,perf_tar)
# Help text displayed when executing 'make help'
# ---------------------------------------------------------------------------
help: FORCE
@echo ' rpm-pkg - Build both source and binary RPM kernel packages'
@echo ' binrpm-pkg - Build only the binary kernel package'
@echo ' deb-pkg - Build the kernel as a deb package'
@echo ' tar-pkg - Build the kernel as an uncompressed tarball'
@echo ' targz-pkg - Build the kernel as a gzip compressed tarball'
@echo ' tarbz2-pkg - Build the kernel as a bzip2 compressed tarball'
@echo ' tarxz-pkg - Build the kernel as a xz compressed tarball'
@echo ' perf-tar-src-pkg - Build $(perf-tar).tar source tarball'
@echo ' perf-targz-src-pkg - Build $(perf-tar).tar.gz source tarball'
@echo ' perf-tarbz2-src-pkg - Build $(perf-tar).tar.bz2 source tarball'
@echo ' perf-tarxz-src-pkg - Build $(perf-tar).tar.xz source tarball'
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...