On Wed, Sep 07, 2022 at 09:33:07PM +0300, Julian Anastasov wrote:
> On Mon, 5 Sep 2022, Jiri Wiesner wrote:
>
> > I believe allowing the kthread the possibility to block in each iteration - for each estimator - introduces some problems:
> > 1. Non-preemptive kernels should be optimized for throughput not for latency
> > Using the figure reported earlier (50,000 services required 200 ms of processing time) it takes roughly 3 ms to process one chain (32 * 1024 / 50 services). The processing time per chain will vary with the number of NUMA nodes and CPUs. Nevertheless, this number comparable with the processing time limit of __do_softirq() - 2 ms, which gets converted to 1 jiffy. In term of latency of non-preemptive kernels, it is entirely resonable to let one chain be processed without rescheduling the kthread.
>
> My worry is that IPVS_EST_MAX_COUNT is not a hard limit,
> we allow this limit to be exceeded when ip_vs_est_add_kthread()
> fails to create kthread (mostly on ENOMEM)
A design decision has been taken to allow more than IPVS_EST_MAX_COUNT estimators in a kthread. The reason is to be able to add estimators even if there is no memory to create a new kthread. Under such memory conditions, user space would not be able to fork new processes - the shell could not execute commands. The system is practically unusable until the OOM killer frees some memory. No production system should be expected to function in a long term when there is not enough memory to fork new processes. The solutions are: add more RAM, decrease workload or resolve memory leak bugs. Not being able to create a kthread can be expected to occur seldom, and it would have to occur while services or destination are being reconfigured. So, why bother with allowing more than IPVS_EST_MAX_COUNT estimators in a kthread. It is common to return -ENOMEM to user space under such conditions.
> or if we add a limit
> for kthreads, so in such cases we can not refuse to add more
> estimators to existing kthreads.
As for limiting the number of kthreads, the limit could implemented as a sysctl variable. The default should be large enough for most deployments. I guess it could accomodate more than 900,000 estimators, which means 30 kthreads. The maximum number of destinations I have seen on a system was 110,000, with 7,000 services (but I have not seen many production systems running IPVS).
The current design does not take into account estimators that have been removed. As a result, kthreads that are not the last kthread could have fewer than IPVS_EST_MAX_COUNT estimators. This could be prevented by changing ipvs->est_add_ktid in ip_vs_stop_estimator() if the value of est->ktid is lower than the current ipvs->est_add_ktid. Ip_vs_start_estimator() would have to increment ipvs->est_add_ktid until it finds a kthread with fewer than IPVS_EST_MAX_COUNT estimators or it has to create a new kthread.
> > 3. Blocking while in ip_vs_estimation_chain() will results in wrong estimates for the remaining estimators in a chain. The 2 second interval would not be kept, rate estimates would be overestimated in that interval and underestimated in one of the future intervals.
> > In my opinion, any of the above reasons is sufficient to remove ip_vs_est_cond_resched_rcu(), ip_vs_est_wait_resched() and kd->mutex.
>
> The chains can become too long. I'm not sure it is
> good to avoid cond_resched() for long time. Another solution
> would be to allocate more chains for a tick and apply some
> hard limit for these chains. cond_resched() will be called
> after such chain is processed. But it is difficult to
> calculate hard limit for these chains, it depends on the
> cycles we spend (CPU speed and the number of possible CPUs
> we walk in the loop). For example, we can have again 50 ticks
> but 16 chains per tick, so total 800 chains per kthread (50*16).
> 32*1024/800 means 40 estimators per chain before calling
> cond_resched().
OK, this seems workable. All the chains could be in one array
struct hlist_head chains[IPVS_EST_NCHAINS * 16];
and you would increment row by 16 in ip_vs_estimation_kthread().
> And a tick can attach more than 16 chains
> if the est_max_count is exceeded. It will cost some memory
> to provide more chains but it will avoid the kd->mutex
> games.
>
> struct hlist_head *tick_chain = &kd->tick_chains[row];
>
> rcu_read_lock();
> /* tick_chains has no limit of chains */
> hlist_for_each_entry_rcu(chain, tick_chains, list) {
> /* This list below is limited */
> hlist_for_each_entry_rcu(e, &chain->ests, list) {
> ...
> if (kthread_should_stop())
> goto end;
> ...
> }
> cond_resched_rcu();
> }
So, you set a limit - IPVS_EST_MAX_COUNT - but you also allow this limit to be ignored because of a corner case. As a result, tick_chains must not have a limit of chains because of that. I lean towards keeping the maximum of IPVS_EST_MAX_COUNT estimators per kthread.
There is an alternative design where you could increase kd->est_max_count for all kthreads once all of the available kthreads have kd->est_max_count estimators. Nevertheless, there would also have to be a limit to the value of kd->est_max_count. Imagine the estimation during a single tick would take so long that the gap variable in ip_vs_estimation_kthread() would become negative. You would need to have circa 250,000 estimators per kthread. Since you are already measuring the timeout you need for schedule_timeout() in ip_vs_estimation_kthread(), it should be possible to set the kd->est_max_count limit based on the maximum processing time per chain. It could be half a IPVS_EST_TICK, for example.
But it seems to me that the alternative design - increasing kd->est_max_count - should have some support in what is used in production. Are there servers with more than 983,040 estimators (which would be IPVS_EST_MAX_COUNT * 30 kthreads) or even one third of that?
> If we change ip_vs_start_estimator() to return int err
> we can safely allocate new chains and track for ENOMEM.
> I think, this is possible, with some reordering of the
> ip_vs_start_estimator() calls.
I think ip_vs_start_estimator() should return an int.
> > > Kthread data:
> > >
> > > - every kthread works over its own data structure and all
> > > such structures are attached to array
> >
> > It seems to me there is no upper bound on the number of kthreads that could be forked. Therefore, it should be possible to devise an attack that would force the system to run out of PIDs:
> > 1. Start adding services so that all chains of kthread A would be used.
> > 2. Add one more service to force the forking of kthread B, thus advancing ipvs->est_add_ktid.
> > 3. Remove all but one service from kthread A.
> > 4. Repeat steps 1-3 but with kthread B.
> > I think I could come up with a reproducer if need be.
>
> Agreed, the chains management can be made more robust.
> This patchset is initial version that can serve as basis.
> We should consider such things:
>
> - we do not know how many estimators will be added, if we
> limit the number of kthreads, then they will be overloaded
Not all kthreads would be overloaded. The current desing would add all the excess estimators into the last kthread.
> - add/del can be made to allocate memory for chains, if needed.
> We should not spend many cycles in adding/deleting estimators.
The fewer allocations the better. I would not use a linked list as described above - kd->tick_chains.
> - try more hard to spread estimators to chains, even with
> the risk of applying initially a smaller timer for the newly
> added estimator.
Yes.
> > Unbalanced chains would not be fatal to the system but there is risk of introducing scheduling latencies tens or even hundreds of milliseconds long. There are patterns of adding and removing chains that would results in chain imbalance getting so severe that a handful of chains would have estimators in them while the rest would be empty or almost empty. Some examples:
> > 1. Adding a new service each second after sleeping for 1 second. This would use the add_row value at the time of adding the estimator, which would result in 2 chains holding all the estimators.
> > 2. Repeated addition and removal of services. There would always be more services added than removed. The additions would be carried out in bursts. The forking of a new kthread would not be triggered because the number of services would stay under IPVS_EST_MAX_COUNT (32 * 1024).
> >
> > The problem is that the code does not guarantee that the length of chains always stays under IPVS_EST_MAX_COUNT / IPVS_EST_NCHAINS (32 * 1024 / 50) estimators. A check and a cycle iterating over available rows could be added to ip_vs_start_estimator() to find the rows that still have fewer estimators than IPVS_EST_MAX_COUNT / IPVS_EST_NCHAINS. This would come at the expense of having inaccurate estimates for a few intervals but I think the trade-off is worth it. Also, the estimates will be inaccurate when estimators are added in bursts. If, depending on how services are added and removed, the code could introduce scheduling latencies there would be someone running into this sooner or later. The probability of severe chain imbalance being low is not good enough there should be a guarantee.
>
> About balancing the chains: not sure if it is possible
> while serving some row for current tick, to look ahead and
> advance the current tick work with estimators from the next
> tick. Such decisions can be made every tick. I.e. we do not
> move entries between the chains but we can walk one chain and
> possibly part of the other chain. If we have more chains per
> tick, it will be more easy, for example, if current tick
> processes 16 chains by default, it can process some from the
> next 16 chains, say 16+8 in total. After 2 seconds, this tick can
> process 16+16+8, for example. It will depend on the currently
> added estimators per tick and its chains. Every 2 seconds
> we can advance with one tick, so that an estimator is
> served every 2 seconds or atleast after 1960ms if such
> chain stealing happens. Such logic will allow the
> estimators to be spread in time even while they are attached
> to chains and ticks with different length. As result, we will
> process equal number of estimators per tick by slowly
> adjusting to their current number and chain lengths.
I am definitely not suggesting to implement balancing. I propose that each chain have a hard limit on the number of estimators.
--
Jiri Wiesner
SUSE Labs
