Iirc, in Lisp, closures are heap-allocated, unless they are created at compile-time with macros. Therefore, there is the added overhead of malloc and free calls with each closure created. Am I wrong here?
Definitely. Lisp is a family of languages that has now existed for almost 70 years. There simply isn't one way that closures work in "Lisp". Some implementations of languages in the lisp family have compilers that have sophisticated ways of handling closures. They carefully classify what is or is not captured by closure (and what is shared with other closures and what is mutably shared), and try to guess whether a closure can escape from the environment where it's created. Different code generation strategies, and strategies for representing the environment, apply to different situations.
Yes, in that normal closures being stack or heap allocated is an implementation detail; at least in CL. SBCL can stack allocate some closures if DYNAMIC-EXTENT is used: https://www.sbcl.org/manual/#Stack-allocation-1
Or I believe if it can determine the closure has dynamic extent, for example if it's passed to a standard function for which it knows the closure will not escape.