Isn't paging orthogonal to using brk? Or is "paging" something more specific than "virtual memory is handled by the OS in big chunks"?

I guess your allocator can try its best to prevent fragmentation, but you're right that returning memory to the OS isn't going to happen without explicit compaction (which nobody in native code is going to do.) Dunno if anyone ever expects memory use to go down though.

(Is less true than it used to be? -- I guess we used to make big swap files and now that's less fashionable.)

I guess if it's not too much more of a burden on the OS to make it keep track of a Swiss cheese virtual memory allocation then it is useful.