Comment 22 for bug 1350522

So I guess the next question would be whether in all 95% which do work (deducted from the ~5% failing), are all Xen version != 4.2 or a mix of versions, including 4.2? At least the fact that this persists while only rebooting make some hypervisor code involvement likely.

The log looks to me like further prove that it is systemd-udevd itself at the bottom of the problem. Which probably should not surprise me with the usual tendency of taking over the world that systemd seems to have. So the systemd-udevd is loading a module, when it gets this. We can see it is a vmalloc. So the size of the area is not that critical.
All the cases I looked at had: vmalloc: "allocation failure, allocated 20480 of 24576 bytes" after the first trace. The way I understand that first warning is: we got some space to store a PTE (page table entry) but that slot seems to already (or still) contain a valid entry. This would be returned as -EBUSY.

After the warning about the PTE, the two lines about the allocation failure are printed:
  vmalloc: allocation failure, allocated 20480 of 24576 bytes
  systemd-udevd: page allocation failure: order:0, mode:0xd2

The order-0 allocation is a bit odd. The flags/mode I would decode as:
  GFP_KERNEL(__GFP_WAIT|__GFP_IO|__GFP_FS)|__GFP_HIGHMEM

So a normal kernel page allocation (that should wait) trying for highmem (which should fallback for normal->dma32->dma). Not sure about what exactly the memory printouts tell us. Will try to chat with Andy about those. But more or less this sequence seems to repeat with varying amounts of requested/returned memory. So a bit weird that a) a normal order-0 allocation fails and this only happens in a few cases.