Is there any reason this c recursive function generates this pagefault?

Question

So I want to write recursive syscall in c which gets all descendands from a process (kids, grandkids, ..). System which I'm using is Minix 3.2.1, but I don't think it should be much different from most UNIX systems. However my function throws very ugly error. The code is as follows:

int do_whoMaxDescendants(void)
{
  int maxChildren = 0;
  pid_t found = -1;

  for (int proc_nr = 0; proc_nr < NR_PROCS; ++proc_nr)
  {
    if (mproc[proc_nr].mp_flags & IN_USE)
    {
      int children = kidCount(proc_nr);
      if (children > maxChildren)
      {
        maxChildren = children;
        found = mproc[proc_nr].mp_pid;
      }
    }
  }
  return found;
}

int kidCount(int currParent)
{
  int children = 0;
  for (int nextParent = 0; nextParent < NR_PROCS; ++nextParent)
  {
    if ((mproc[nextParent].mp_flags & IN_USE) && (mproc[nextParent].mp_parent == currParent))
    {
      children++;
      children = kidCount(nextParent) + children;
    }
  }
  return children;
}

And the error looks like this:

Curious, why `int do_whoMaxDescendants()` and not `pid_t do_whoMaxDescendants()`? — chux - Reinstate Monica, Nov 20 '21 at 20:54
In systems I am aware of and in this one as well pid_t is basically signed int, for my needs int suffices — Johnny, Nov 20 '21 at 21:02
Should you want your code to work on many systems, consider [this](https://stackoverflow.com/a/34938359/2410359). — chux - Reinstate Monica, Nov 20 '21 at 22:12
[Edit] the question to include the error _as text_, not an image. What is `mproc`? — 1201ProgramAlarm, Nov 20 '21 at 22:13
Unfortunetly I am unable to copy error from my virtual machine, hence I copied a screenshot of this. ```mproc``` is a fancy structure with a lot of information about processes in system, however for needs of this snippet just say it can tell us if procces is in use and who is the parent of that process — Johnny, Nov 20 '21 at 22:20
So this is running inside the kernel? I don't know about Minix specifically, but it's common that kernels run with a very small amount of kernel stack space, maybe only a few KB. So even a fairly small recursion, that might be no problem in userspace, can cause a stack overflow in the kernel. I would suggest you rewrite your function with an iterative algorithm. — Nate Eldredge, Nov 20 '21 at 22:39
It's suspicious that the faulting address is the last 32-bit word of a page, which is what you would see if the stack (growing down) had run off the last mapped page allocated to it, and you were now pushing to the next unmapped page below it. A register dump that shows the stack pointer would help confirm that. — Nate Eldredge, Nov 20 '21 at 22:42
It is running inside the kernel. However I'm not sure how to make it run outside of it as it uses ```mproc``` which is defined inside the ```misc.c``` file where this function is written. Also unfortunetly I'm just starting my adventure with UNIX systems so I'm not sure how to get a register dump, but what you have just told me would explain quite a few things. Sadly as I said, I'm not sure how to make use of them — Johnny, Nov 20 '21 at 23:58

Whooper · Accepted Answer · 2022-11-13T10:40:39.210

2

[EDIT] For future generations, for example process INIT is its own parent so calling kidCount on INIT triggers infinity loop. You have to add extra statement to if in KidCount e.g. (process_ID != Parent_process_ID)

edited Nov 13 '22 at 10:40

answered Nov 07 '22 at 22:49

Whooper

36
4

Yeah, I shouldve updated this question when I figured it out. Thank you for input. Also I probably recognise a fellow WUT student lurking here – Johnny Nov 08 '22 at 23:30
I glad we could contribute together – Whooper Nov 10 '22 at 10:57
@Whooper, Could you clarify your answer? Instead of using the term 'him', you could call out the specific function. As well, it might be confusing using the term 'instance' since that is also the term used in an OOP paradigm. While OOP is not involved in this specific example, being specific and not mixing nomenclature could help future people who have a similar question. – Spectrem Nov 12 '22 at 04:43
As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Nov 12 '22 at 04:43

score 1 · Answer 2 · answered Nov 21 '21 at 02:07

You are writing Minix kernel code. The Minix kernel stack is 4096 bytes. Any significant recursion is likely to overflow it, and that's probably the cause of your page fault. Note the faulting address is near the end of a page, probably the next page below the stack page, which may be an unmapped guard page so that a stack overflow panics before corrupting other data.

So you will need to come up with an algorithm that doesn't use recursion.

Is there any reason this c recursive function generates this pagefault?

2 Answers2