API tools faq
paste
cr88192

TestKern Page Translation B-Tree (experimental)

cr88192
Mar 24th, 2022
1,160
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 7.10 KB | None | 0 0
raw download clone embed print report
  1. /*
  2. B-Tree intended for Virtual Address Translation.
  3. Trying to make its speed passable...
  4.  */
  5.  
  6. #if (TKMM_PAGEBITS==12)
  7. #define TK_VMABTREE_NODESZ      202
  8. #define TK_VMABTREE_NODEFULL    200
  9. #define TK_VMABTREE_NODEPAD2    24
  10. #endif
  11.  
  12. #if (TKMM_PAGEBITS==14)
  13. #define TK_VMABTREE_NODESZ      816
  14. #define TK_VMABTREE_NODEFULL    814
  15. #define TK_VMABTREE_NODEPAD2    32
  16. #endif
  17.  
  18. #if (TKMM_PAGEBITS==16)
  19. #define TK_VMABTREE_NODESZ      3274
  20. #define TK_VMABTREE_NODEFULL    3272
  21. #define TK_VMABTREE_NODEPAD2    24
  22. #endif
  23.  
  24. typedef struct TK_VmaBTreeNode_s TK_VmaBTreeNode;
  25. struct TK_VmaBTreeNode_s {
  26. u64     npt_next;   //0000
  27. u64     npt_prev;   //0008
  28. u64     npt_up;     //0010
  29. u16     n_ecnt;     //0018, Entry Count
  30. byte    level;      //001A
  31. byte    pad1[5];    //001B
  32. byte    pad2[TK_VMABTREE_NODEPAD2];     //0020..
  33. u32     addr_hi[TK_VMABTREE_NODESZ];    //..
  34. u64     addr_lo[TK_VMABTREE_NODESZ];    //..
  35. u64     pte_val[TK_VMABTREE_NODESZ];    //..
  36. };
  37.  
  38. u64 TK_VMem_GetBTreePageTableEntry(s64 ttb, u64 teal, u64 teah)
  39. {
  40.     TK_VmaBTreeNode *head;
  41.     u64 *addrlo;
  42.     u32 *addrhi;
  43.     u64 va_lo, pva_lo;
  44.     u32 va_hi, pva_hi;
  45.     u64 pte;
  46.     int i, j, k, m, n;
  47.  
  48.     head=(TK_VmaBTreeNode *)TK_VMem_PtrForPto(ttb);
  49.    
  50.     va_lo=(teal&0x0000FFFFFFFFFFFFULL)|(teah<<48);
  51.     va_hi=(teah>>16);
  52.     va_lo&=~((1ULL<<TKMM_PAGEBITS)-1);
  53.    
  54.     while(1)
  55.     {
  56.         addrhi=head->addr_hi;
  57.         addrlo=head->addr_lo;
  58.         pva_hi=-1;
  59.         pva_lo=-1;
  60.  
  61.         /* Binary search for address. */
  62.         m=0; n=head->n_ecnt;
  63.         i=(m+n)>>1;
  64.         while((n-m)>1)
  65. //      while(n>m)
  66.         {
  67.             i=(m+n)>>1;
  68.             pva_hi=addrhi[i];
  69.             pva_lo=addrlo[i];
  70.  
  71.             if(va_hi<pva_hi)
  72.                 { n=i; continue; }
  73.             if(va_hi>pva_hi)
  74.                 { m=i; continue; }
  75.  
  76.             if(va_lo<pva_lo)
  77.                 { n=i; continue; }
  78.             if(va_lo>pva_lo)
  79.                 { m=i; continue; }
  80.  
  81.             if(!head->level)
  82.             {
  83.                 pte=head->pte_val[i];
  84.                 return(pte);
  85.             }
  86.  
  87.             break;
  88.         }
  89. //      i=(m+n)>>1;
  90.  
  91. #if 1
  92.         if((va_lo!=pva_lo) || (va_hi!=pva_hi))
  93.         {
  94.             i=m;
  95.             while(i<n)
  96.             {
  97.                 pva_hi=addrhi[i+1];
  98.                 pva_lo=addrlo[i+1];
  99.                 if(pva_hi>va_hi)
  100.                     break;
  101.                 if(pva_lo>va_lo)
  102.                     break;
  103.                 i++;
  104.             }
  105.             pva_hi=addrhi[i];
  106.             pva_lo=addrlo[i];
  107.         }
  108. #endif
  109.  
  110.         /* Break out of loop at bottom of tree. */
  111.         if(!head->level)
  112.             break;
  113.        
  114.         /* Next node down. */
  115.         pte=head->pte_val[i];
  116.         head=(TK_VmaBTreeNode *)TK_VMem_PtrForPto(pte);
  117.     }
  118.  
  119.     if((va_hi==pva_hi) && (va_lo==pva_lo))
  120.     {
  121.         pte=head->pte_val[i];
  122.         return(pte);
  123.     }
  124.     return(0);
  125. }
  126.  
  127. int TK_VMem_SetBTreePageTableEntry(s64 ttb, u64 teal, u64 teah, u64 ptval)
  128. {
  129. //  TK_VmaBTreeNode *headstk[16];
  130.     TK_VmaBTreeNode *head, *head1, *head2;
  131.     u64 *addrlo, *addrpt;
  132.     u32 *addrhi;
  133.     u64 va_lo, pva_lo;
  134.     u32 va_hi, pva_hi;
  135.     u64 pte, pte1, pte2, hptd;
  136.     int i, j, k, m, n, hsp;
  137.  
  138. //  if(sizeof(TK_VmaBTreeNode)!=(1<<TKMM_PAGEBITS))
  139. //  {
  140. //      printf("Node Size Bad, %d\n", sizeof(TK_VmaBTreeNode));
  141. //  }
  142.  
  143.     head=(TK_VmaBTreeNode *)TK_VMem_PtrForPto(ttb);
  144.     hptd=ttb;
  145.  
  146.     va_lo=(teal&0x0000FFFFFFFFFFFFULL)|(teah<<48);
  147.     va_hi=(teah>>16);
  148.     va_lo&=~((1ULL<<TKMM_PAGEBITS)-1);
  149.  
  150.     n=head->n_ecnt;
  151.     if(n>=TK_VMABTREE_NODEFULL)
  152.     {
  153.         /* Split Top-Level Node */
  154.    
  155.         head1=TKMM_PageAlloc(1<<TKMM_PAGEBITS);
  156.         head2=TKMM_PageAlloc(1<<TKMM_PAGEBITS);
  157.         pte1=TK_VMem_PtoForPtr((void *)head1)|1;
  158.         pte2=TK_VMem_PtoForPtr((void *)head2)|1;
  159.  
  160.         memcpy(head1, head, 1<<TKMM_PAGEBITS);
  161.  
  162.         head1->npt_next=pte2;
  163.         head2->npt_prev=pte1;
  164.         head2->level=head1->level;
  165.  
  166.         j=head1->n_ecnt>>1;
  167.         for(k=j; k<head1->n_ecnt; k++)
  168.         {
  169.             pva_hi=head1->addr_hi[k];
  170.             pva_lo=head1->addr_lo[k];
  171.             pte=head1->pte_val[k];
  172.             head2->addr_hi[k-j]=pva_hi;
  173.             head2->addr_lo[k-j]=pva_lo;
  174.             head2->pte_val[k-j]=pte;
  175.         }
  176.  
  177.         head2->n_ecnt=head1->n_ecnt-j;
  178.         head1->n_ecnt=j;
  179.  
  180.         pva_hi=head1->addr_hi[0];
  181.         pva_lo=head1->addr_lo[0];
  182.         head->addr_hi[0]=pva_hi;
  183.         head->addr_lo[0]=pva_lo;
  184.         head->pte_val[0]=pte1;
  185.  
  186.         pva_hi=head2->addr_hi[0];
  187.         pva_lo=head2->addr_lo[0];
  188.         head->addr_hi[1]=pva_hi;
  189.         head->addr_lo[1]=pva_lo;
  190.         head->pte_val[1]=pte2;
  191.         head->n_ecnt=2;
  192.         head->level=head1->level+1;
  193.  
  194.         head->addr_hi[2]=-1;
  195.         head->addr_lo[2]=-1;
  196.     }
  197.  
  198. //  hsp=0;
  199.     while(1)
  200.     {
  201. //      headstk[hsp++]=head;
  202.    
  203.         addrhi=head->addr_hi;
  204.         addrlo=head->addr_lo;
  205.         addrpt=head->pte_val;
  206.  
  207.         m=0; n=head->n_ecnt;
  208.         while((n-m)>1)
  209.         {
  210.             i=(m+n)>>1;
  211. //          pva_hi=head->addr_hi[i];
  212. //          pva_lo=head->addr_lo[i];
  213.             pva_hi=addrhi[i];
  214.             pva_lo=addrlo[i];
  215.  
  216.             if(va_hi<pva_hi)
  217.                 { n=i; continue; }
  218.             if(va_hi>pva_hi)
  219.                 { m=i; continue; }
  220.  
  221.             if(va_lo<pva_lo)
  222.                 { n=i; continue; }
  223.             if(va_lo>pva_lo)
  224.                 { m=i; continue; }
  225.             break;
  226.         }
  227.  
  228. #if 1
  229.         i=m;
  230.         while(i<n)
  231.         {
  232. //          pva_hi=head->addr_hi[i+1];
  233. //          pva_lo=head->addr_lo[i+1];
  234.             pva_hi=addrhi[i+1];
  235.             pva_lo=addrlo[i+1];
  236.             if(pva_hi>va_hi)
  237.                 break;
  238.             if(pva_lo>va_lo)
  239.                 break;
  240.             i++;
  241.         }
  242. //      pva_hi=head->addr_hi[i];
  243. //      pva_lo=head->addr_lo[i];
  244.         pva_hi=addrhi[i];
  245.         pva_lo=addrlo[i];
  246. #endif
  247.  
  248.         if(!head->level)
  249.             break;
  250.  
  251.         pte=head->pte_val[i];
  252.         head1=(TK_VmaBTreeNode *)TK_VMem_PtrForPto(pte);
  253.         if(head1->n_ecnt<TK_VMABTREE_NODEFULL)
  254.         {
  255.             /* Continue down tree if child node is not full. */
  256.             hptd=pte;
  257.             head=head1;
  258.             continue;
  259.         }
  260.  
  261.         /* If Node is almost full, Split Node */
  262.         head2=TKMM_PageAlloc(1<<TKMM_PAGEBITS);
  263.         pte1=TK_VMem_PtoForPtr((void *)head2)|1;
  264.  
  265.         head2->npt_next=head1->npt_next;
  266.         head1->npt_next=pte1;
  267.         head2->npt_prev=pte;
  268.         head2->level=head1->level;
  269.  
  270.         j=head->n_ecnt++;
  271.         while(j>i)
  272.         {
  273.             pva_hi=addrhi[j-1];
  274.             pva_lo=addrlo[j-1];
  275.             pte=addrpt[j-1];
  276.             if(pva_hi<va_hi)
  277.                 break;
  278.             if(pva_lo<va_lo)
  279.                 break;
  280.             addrhi[j]=pva_hi;
  281.             addrlo[j]=pva_lo;
  282.             addrpt[j]=pte;
  283.             j--;
  284.         }
  285.  
  286.         k=head1->n_ecnt>>1;
  287.         pva_hi=head1->addr_hi[k];
  288.         pva_lo=head1->addr_lo[k];
  289.         head->addr_hi[j]=pva_hi;
  290.         head->addr_lo[j]=pva_lo;
  291.         head->pte_val[j]=pte1;
  292.  
  293.         j=head->n_ecnt;
  294.         head->addr_hi[j]=-1;
  295.         head->addr_lo[j]=-1;
  296.  
  297.         k=head1->n_ecnt;
  298.         j=head1->n_ecnt>>1;
  299. #if 0
  300.         for(k=j; k<=head1->n_ecnt; k++)
  301.         {
  302.             pva_hi=head1->addr_hi[k];
  303.             pva_lo=head1->addr_lo[k];
  304.             pte=head1->pte_val[k];
  305.             head2->addr_hi[k-j]=pva_hi;
  306.             head2->addr_lo[k-j]=pva_lo;
  307.             head2->pte_val[k-j]=pte;
  308.         }
  309. #endif
  310.  
  311.         k=(k-j)+1;
  312.         memcpy(head2->addr_hi, head1->addr_hi+j, k*sizeof(u32));
  313.         memcpy(head2->addr_lo, head1->addr_lo+j, k*sizeof(u64));
  314.         memcpy(head2->pte_val, head1->pte_val+j, k*sizeof(u64));
  315.  
  316.         head2->n_ecnt=head1->n_ecnt-j;
  317.         head1->n_ecnt=j;
  318.         head1->addr_hi[j]=-1;
  319.         head1->addr_lo[j]=-1;
  320.  
  321. //      j=head2->n_ecnt;
  322. //      head2->addr_hi[j]=-1;
  323. //      head2->addr_lo[j]=-1;
  324.  
  325. //      pva_hi=head2->addr_hi[0];
  326. //      pva_lo=head2->addr_lo[0];
  327. //      head->addr_hi[i+1]=pva_hi;
  328. //      head->addr_lo[i+1]=pva_lo;
  329. //      head->pte_val[i+1]=pte1;
  330.     }
  331.  
  332.     if((va_hi==pva_hi) && (va_lo==pva_lo))
  333.     {
  334.         head->pte_val[i]=ptval;
  335.         return(1);
  336.     }
  337.  
  338.     addrhi=head->addr_hi;
  339.     addrlo=head->addr_lo;
  340.     addrpt=head->pte_val;
  341.  
  342.     j=head->n_ecnt++;
  343.     addrhi[j+1]=-1;
  344.     addrlo[j+1]=-1;
  345.  
  346.     while(j>i)
  347.     {
  348.         pva_hi=addrhi[j-1];
  349.         pva_lo=addrlo[j-1];
  350.         pte=addrpt[j-1];
  351.  
  352.         if(pva_hi<va_hi)
  353.             break;
  354.         if(pva_lo<va_lo)
  355.             break;
  356.        
  357.         addrhi[j]=pva_hi;
  358.         addrlo[j]=pva_lo;
  359.         addrpt[j]=pte;
  360.         j--;
  361.     }
  362.  
  363.     addrhi[j]=va_hi;
  364.     addrlo[j]=va_lo;
  365.     addrpt[j]=ptval;
  366.     return(1);
  367. }
  368.  
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!