natsukagami / kjudge

A simple system for hosting competitive programming contests.
GNU Affero General Public License v3.0
23 stars 11 forks source link

Add more tunes for multi-stage problems #95

Open minhnhatnoe opened 1 year ago

minhnhatnoe commented 1 year ago

Is your feature request related to a problem? Please describe.

The current .stage file standard lacks a few controls that is essential to some problems. For example, many 2-steps problems require opening pipes between different stages, such that there is back-and-forth communication between these stages, instead of simply piping the output of the previous stage to the next one.

Describe the solution you'd like

Overall structure

Obviously, there must be a "broker" process to perform validation on the back-and-forth communication of these process and return the corresponding grade. This "broker" process is usually invisible to the contestant. I propose using this "broker" process as the means of distributing data to all stages, and also for measuring time usage (I will discuss this later down below).

From the judging system's PoV, each stage would still have only two standard pipes open, both of these pipes are connected to the "broker" process. Should the problem-setter wish to establish multiple connections between stages, each stage can send the data along with information about the recipient to the broker process in some format. I propose limiting the broker process to C++, and code a wrapper for all piping details. I propose defining another config format.

The config format

The user can define the following objects:

Group

This is an abstraction of cgroups. In short, all stages under a cgroup will share the allotted resource. If no group is defined, all stages are put under a cgroup created using parameters from the problem's config.

The total memory limit of all groups AND the broker process should not exceed the specified memory limit for the problem. This is for ease of config.

Stage

The following can be defined for each stage:

  1. Allowed files (each stage has their own .h file)
  2. Compile command (for each language). Specified with argument list for compiler to support cross-platform compilation.
  3. Run-time arguments.
  4. Group/Limits (If user specify limits, then a new anonymous group is created for the stage)

Broker (singleton)

The following can be defined for the broker process:

  1. Allowed files
  2. Compile command
  3. Limits (the broker cannot be in the same group with the stages)
  4. Maximum waiting time: All sandboxes will be allowed time = maximum waiting time + problem's time limit.

Measuring time usage

Problems with back-and-forth communication are very prone to timing-attacks (I have done this myself in Vietnam TST). To mitigate this, the broker process will have to implement random wait, adding time to execution.

Measuring other resources

The sandbox should be able to receive a custom cgroup to put all stages under a cgroup/Windows Job Object to limit their total memory usage if memory usage for each stage is not configured.

minhnhatnoe commented 1 year ago

By extension, this file format can be used to define custom compile commands, with run-time constants like $OutputFileName to better support all platforms.

natsukagami commented 1 year ago

Unsure about this one -- it seems to hurl a lot of things into one config file. Perhaps this is needed, as communicating processes kind of task is insanely different from everything else.

I think we should narrow this down a little bit: