First off, virtual memory mapping does not necessarily mean "contention free". Kernel memory is virtual too. There's really no difference between kernel and user memory except who gets to use it.

The two ways a process asks the kernel for address space -- brk() and mmap() -- are unavoidably high-overhead. Every kernel call is a task-switch, after all, even mundane things like read()! brk() and mmap() aren't generally bottlenecks, though, because they're called so seldom -- a handful of times to set up libraries, then a call to brk() to assign a large block of undifferentiated memory that the process can use as it pleases without bothering the kernel. You may know this block as the heap segment.

The library function malloc() carves out chunks of the heap segment on demand. It keeps keeps a list of available chunks at the base of the heap. brk() expands the heap in large jumps if it runs out, otherwise the kernel isn't involved at all. Whether there's any contention depends on how malloc() is written.

Most Linux systems use GNU libc, which avoids malloc() contention by using several independent "arenas". I think this amounts to independent heaps.

Now, inside the kernel, there's two basic options for allocating memory depending on your needs - kmalloc() and vmalloc().

kmalloc() is the kernel's cousin of userspace malloc() - more or less a heap kept inside kernel space. It's fast, doesn't change the page table, and lets you avoid contention if absolutely necessary. But you usually can't allocate more than 4 megs at a time(architecture dependent), and the total limit on size might also be as small as 128 megs.

The other is vmalloc(), which alters the page table and forces a synchronization but doesn't have a lot of limits otherwise, since it's not restricted to a chunk of preallocated kernel memory.