Large C codebase – how to organize code?

From the above follows that the modules do not hold global state and communicate with each other through well-defined interfaces - and not through global state.

Unfortunately C does not have an actual module system but only the "unit of translation" concept. In general you want two files per module e.g. my_module.c and my_module.h and prefix everything in there with my_module to avoid namespace conflicts e.g. my_module_new_foo(), my_module_update_foo(foo, MY_MODULE_FLAG | MY_MODULE_OTHER_FLAG)

EDIT: Note that the standard scheme to avoid holding global state in a module is that the module provides a function which allocates an "instance" of the module and all module functions work on such "instances" e.g.

  RNG_INSTANCE* r = rng_new();
  double v = rng_uniform(r);
  ...
  rng_free(r);