C calling convention: who cleans the stack in variadic functions vs normal functions?

as far as I am concerned, C does use cdecl

Its name notwithstanding, the cdecl convention is not universal for C code, not even on the x86 architecture. It has the advantage of being simple to define and implement, but it makes no use of CPU registers for argument passing, which is more efficient. That makes a difference even on register-starved x86, but it makes a lot more difference on architectures with more available registers, such as x86_64.

Talking about the cleanup, here is my question. I do not understand: are there three different things?

1. stack clean
2. moving the pointer back to the penultimate stack frame
3. stack restoration

Or how should I see them?

I would be inclined to interpret (1) and (3) as different ways of saying the same thing, but it is conceivable that someone would draw distinctions between them. (3) and related wording is what I encounter most frequently. (2) is not necessarily the same thing, because there may be two relevant stack parameters to be restored: the base of the stack frame (see below), and the top of the stack. The stack frame base is important in the event that the stack frame contains more information than argument and local variable values, such as the base of the previous stack frame.

Also, the target of this question is basically how could variadic function works in calling conventions like Pascal or stdcall where the callee should clear / clean / restore (I don't know which operation) the stack - but he doesn't know how many parameters it will receive.

The stack is not necessarily the whole picture.

The callee cannot restore the stack if it does not know how to find the top of its caller's stack, and, if necessary, the base of its caller's stack frame. But in practice, this is usually hardware assisted.

Taking x86 (for which cdecl was designed) as an example, the CPU has registers for both the stack (frame) base and the current stack pointer. The caller's stack base is stored on the stack at a known offset (0) from the callee's stack base. Regardless of the number of arguments, the callee restores the stack by moving the top of the stack to its own stack base, and popping the value there to obtain the caller's stack base.

It is conceivable, however, that there is a calling convention in use somewhere that affords no way to restore the stack to a chosen previous state other than to pop elements one at a time, that does not explicitly convey the number of arguments to the called function, and that requires the callee to restore the caller's stack. Such a calling convention would not support variadic functions.

Why is it so important the order in which parameters are pushed on to the stack?

The order is not important in any general sense, but it is essential for caller and callee, which may be compiled separately, to agree about it. Otherwise, the callee cannot match the passed values with the parameters they are intended for. Thus, to whatever extent a calling convention relies on the stack, it must specify precisely which arguments are passed there, and in which order.

Regarding stack frames: this is more material that is not specified by C and that varies, at least to some extent. Conceptually, though, the stack frame of a function call is the portion of the stack that provides execution context for that call. It typically supplies storage for local variables, and it may contain additional information, such as a return address and / or the value of the caller's stack frame pointer. It might also contain other per-function-call information appropriate for the execution environment. Details are part of the calling convention in use.