Every mark and make deoptimized call follow this pattern (with the exception of klass unloading, see below):
bool anything_deoptimized = false;
{
  NoSafepointVerifier nsv;
  assert_locked_or_safepoint(Compile_lock);
  mark_nmethods();
  anything_deoptimized = deoptimize_all_marked();
}
if (anything_deoptimized) {
  run_deoptimize_closure();
}

Where mark_nmethods is the custom code for every call site that has some way of selecting nmethods and marking them for deoptimization.

deoptimize_all_marked will then run and take all selected/marked nmethods and make them not entrant and call make_deoptimized.

Then if any nmethod was marked the DeoptimizeMarkedClosure will be run.

The proposal is to encapsulate this logic in one place and only allow access to the mark for deoptimization code from this place. The mark_nmethods is provided by the user that wants to deoptimize something and the rest of the logic is done by the encapsulation. 

This patern and along with the stability and mutual exclusion guarantees from 
  NoSafepointVerifier nsv;
  assert_locked_or_safepoint(Compile_lock);
allows for deoptimize_all_marked to not have to walk the whole code cache and can instead just remember what nmethods the mark_nmethods code marked. 

The Exception:
The klass unloading code currently sets the mark for deoptimzation flag on nmethods that depend on the klass being unloaded. That however is all it does, there is no guarantee that those nmethods will become not entrant and make_deoptimized. The current implementation may if some future deoptimization happens to trigger see these marks as it scans the whole code cache, but it is never triggered from klass unloading. 

Me and [~eosterlund] discussed this and this behaviour seems like some leftover from earlier versions of klass unloading. There should be no reason to eliminate the nmethods that depend on unloaded klasses except to eliminate dead code. It is probably better to let other mechanisms decide if an nmethod with dead code should be deoptimized than the klass unloading. 

It might be a future improvement to have some stats which record that an nmethod had some dependency to an unloaded klass which might effect the heuristic for selecting what methods are deoptimized.