小编R..*_*R..的帖子

我正在研究一种基于Select算法的快速变量实现,用于选择一个好的枢轴元素.传统智慧似乎是将数组划分为5个元素块,取每个元素的中位数,然后递归地将相同的阻塞方法应用于得到的中位数以获得"中位数中位数".

令我困惑的是选择5元素块而不是3元素块.对于5元素块,在我看来,你执行n/4 = n/5 + n/25 + n/125 + n/625 + ...5个中值运算,而对于3个元素块,你执行n/2 = n/3 + n/9 + n/27 + n/81 + ...3个中值运算.由于每个5的中位数是6个比较,并且每个中位数3是2个比较,这导致3*n/2使用5的n中位数和使用3的中位数进行比较.

任何人都可以解释这种差异,使用5元素块的动机是什么？我不熟悉应用这些算法的常规做法,所以也许你可以通过某种方式减少一些步骤,并且仍然能够"足够接近"中位数以确保良好的转向,并且这种方法可以更好地使用5元素块？

在POSIX线程的大多数实现中,在新创建的线程处于能够运行应用程序代码的一致状态之前,需要进行一些初始化.这可能涉及解锁线程结构中的锁,在使用一个的实现中初始化"线程寄存器",初始化线程本地数据(编译器级别的TLS或POSIX线程特定的数据)等.我找不到清楚的保证在线程可以接收任何信号之前完成所有这些初始化; 我能找到的最接近的是2.4.3:

下表定义了一组异步信号安全的函数.因此,应用程序可以无限制地调用信号捕获功能:

...

据推测,这些函数中的一些(至少fork必须检查由pthread_atfork函数建立的全局状态)取决于线程处于一致的初始化状态.

困扰我的一件事是我已经阅读了很多glibc/nptl源代码,并且找不到任何显式同步来防止新创建的线程在完全初始化之前处理信号.我希望线程调用pthread_create在调用之前阻塞所有信号clone,并且一旦初始化完成,新线程就会解除阻塞它们,但是我找不到任何代码,也没有在strace输出中看到它.

我需要在close可能被信号处理程序(有或没有SA_RESTART)中断的情况下调查/测试Linux上某些代码的行为.什么是最方便的设置,使close系统调用睡眠在一个可测量的时间窗口,在此期间,我可以尝试用信号命中过程？一些想法:

• 故意缓慢/无响应的NFS安装
• 自定义FUSE驱动程序

但是,由于这些设置有点痛苦,我想知道是否有更多现成的我可以使用它可以提供所需的行为.

尽管涉及两个子部分,但我认为这是一个综合问题,因为它被分解成部分的方式并不重要.只要最终结果保留了所有有意义的历史记录以及检查,研究和构建/测试历史版本的能力,我就会以不同的方式实现我想要的目标.目标是退出hg和到目前为止使用的subrepo模型,然后转移到git中的统一树,但不会牺牲历史记录.

我开始的是一个Mercurial存储库,它包含一些顶级代码和许多有趣历史所在的子存储库.subrepos有一些分支/合并,但没有什么太疯狂.我想要实现的最终结果是单个git存储库,没有子模块,这样:

• 对于原始顶级hg repo中的每个提交,都有一个git提交,它会检查完全相同的树,因为您将检查相应的hg提交及其所有引用subrepo提交.

• 这些对应于连续顶级hg提交的git提交是彼此的后代,其提交对应于其间的所有相关子提交.

我对如何实现这一点的基本思想是迭代所有顶级hg提交,并且对于每个更改的顶级提交.hgsubstate,也迭代从旧修订到子模块的新修订的所有路径(可能涉及分枝).在每一步:

• 查看顶级和所有子目录的相应hg修订版.
• 从git索引中删除所有内容.
• 将从hg检出的所有内容都放到git索引中.
• 使用git-write-tree和git-commit-tree生成具有所需父级的提交,使用来自相应hg提交的authors,date和commit消息.
• 记录新git commit和hg提交之间的对应关系,以用于生成未来提交的父项.

这有用吗？有没有更好的方法来实现我想要的,也许首先用hg做subrepo崩溃？我不清楚的最重要的事情是如何执行所需的迭代,所以如何实现它的实用建议将是伟大的.

一个额外的约束:原始存储库涉及无法发布的内容(这是git-filter-branch基本转换完成后的额外步骤)所以涉及上传存储库以供第三方处理的解决方案是不可行的.

来自C标准的未定义行为的示例之一(J.2):

- 数组下标超出范围,即使一个对象显然可以使用给定的下标访问(如左边的表达式a [1] [7],给出声明int a [4] [5])(6.5.6)

如果声明从更改int a[4][5]为unsigned char a[4][5],访问a[1][7]仍会导致未定义的行为吗？我的意见是,它没有,但我从其他人那里听到了不同意见,我想看看其他一些想成为专家的想法.

我的推理:

• 根据6.2.6.1第4段和第6.5段第7段的通常解释,对象的表示a是sizeof (unsigned char [4][5])*CHAR_BIT位,可以作为unsigned char [20]与对象重叠的类型数组进行访问.

• a[1]将type unsigned char [5]作为左值,但在表达式中使用(作为运算[]符的操作数,或等效地作为运算+符的操作数*(a[1]+7)),它衰减为类型的指针unsigned char *.

• 值a[1]也是指向a表单中"表示"的字节的指针unsigned char [20].以这种方式解释,添加7 a[1]是有效的.

在不保留当前线程列表的情况下,我试图看到实时信号被传递到我的进程中的所有线程.我的想法是这样做:

• 最初安装信号处理程序并在所有线程中解除阻塞信号.
• 当一个线程想要发送"广播"信号时,它获取互斥锁并设置广播发生的全局标志.
• 发送器pthread_sigmask为自己阻塞信号(使用),并重复进入循环调用,raise(sig)直到sigpending指示信号处于挂起状态(信号被阻止时没有剩余线程).
• 当线程接收到信号时,它们会对其进行操作,但在信号处理程序中等待广播标志被清除,这样信号将保持屏蔽状态.
• 发送者通过解锁信号来完成循环(以便获得自己的传送).
• 当发送方处理自己的信号时,它会清除全局标志,以便所有其他线程可以继续其业务.

我遇到的问题pthread_sigmask是没有得到尊重.如果我运行测试程序strace(可能是由于不同的调度时间),一切正常,但是一旦我单独运行它,发送者就会收到自己的信号(尽管已经阻止了它？？)并且没有任何其他线程得到预定.

什么想法可能是错的？我尝试使用sigqueue而不是raise探测信号掩码,添加sleep所有地方以确保线程耐心地等待他们的信号等等,现在我不知所措.

编辑:感谢psmears的回答,我想我明白了这个问题.这是一个潜在的解决方案.反馈会很棒:

• 在任何给定的时间,我都可以知道正在运行的线程数,如果需要,我可以阻止所有线程创建和退出广播信号.
• 想要进行广播信号的线程获得锁定(因此没有其他线程可以同时执行),然后阻止信号自身,并向num_threads进程发送信号,然后为自己解除阻塞信号.
• 信号处理程序以原子方式递增计数器,并且信号处理程序的每个实例都等待,直到该计数器等于num_threads返回.
• 执行广播的线程也等待计数器到达num_threads,然后它释放锁定.

一个可能的问题是,如果内核内存不足,信号将不会排队(Linux似乎有这个问题).你知道sigqueue当它无法排队信号时是否可靠地通知呼叫者(在这种情况下我会循环直到它成功),或者信号可能会无声地丢失？

编辑2:它现在似乎正在运作.根据文档sigqueue,EAGAIN如果它无法排队信号,它将返回.但为了稳健性,我决定继续呼叫,sigqueue直到num_threads-1信号处理程序运行,sched_yield在我发送num_threads-1信号之后交错呼叫.

在线程创建时有一个竞争条件,计算新线程,但我用一个奇怪的(ab)使用读写锁解决了它.线程创建是"读取"而广播信号是"正在写入",因此除非有线程尝试广播,否则它不会在创建线程时产生任何争用.

C定义了至少3个级别的"常量表达式":

• 常量表达(不合格)
• 算术常数表达式
• 整数常量表达式

6.6第3段内容如下:

常量表达式不应包含赋值,递增,递减,函数调用或逗号运算符,除非它们包含在未评估的子表达式中.

那么这意味着1,2不是一个恒定的表达式吗？

第8段内容如下:

算术常量表达式应具有算术类型,并且只能具有整数常量,浮点常量,枚举常量,字符常量和sizeof表达式的操作数.算术常量表达式中的转换运算符只能将算术类型转换为算术类型,除非作为sizeof运算符的操作数的一部分,其结果为整数常量.

什么是操作数(union { uint32_t i; float f; }){ 1 }.f？如果1是操作数,那么这可能是一个算术常量表达式,但如果{ 1 }是操作数,则显然不是.

编辑:另一个有趣的观察:7.17第3段要求结果是offsetof类型的整数常量表达式size_t,但offsetof据我所知,标准实现不需要是标准的整数常量表达式.这当然是可以的,因为允许实现(在6.6第10段下)接受其他形式的常量表达式,或者实现offsetof宏__builtin_offsetof而不是通过指针减法.但是,这种观察的本质是,如果你想offsetof在需要整数常量表达式的上下文中使用,你真的需要使用实现提供的宏而不是自己的.

我发现在Linux上,通过自己调用rt_sigqueue系统调用,我可以在si_uid和si_pid字段中放入我喜欢的任何内容,并且调用成功并愉快地传递不正确的值.当然,发送信号的uid限制提供了一些防止这种欺骗的保护,但我担心依赖这些信息可能是危险的.关于我能读到的主题,有没有好的文件？为什么Linux允许调用者指定siginfo参数而不是在内核空间中生成它们的明显不正确的行为？这似乎是荒谬的,特别是因为可能需要额外的sys调用(因此性能成本)才能在用户空间中获取uid/gid.

编辑:基于我对POSIX的阅读(我强调):

如果si_code是SI_USER或SI_QUEUE,[XSI]或小于或等于0的任何值,则信号由进程生成,si_pid和si_uid 应分别设置为进程ID和发送方的真实用户ID.

我相信Linux的这种行为是不符合的并且是一个严重的错误.

假设pid X是一个进程组负责人并X终止,但进程组中的其他进程仍在运行(X作为他们的pgid).Linux会阻止将值X指定为新进程的pid吗？

我问这是因为POSIX允许的失败条件setsid:

[EPERM]调用进程已经是进程组负责人,或者调用进程以外的进程的进程组ID与调用进程的进程ID匹配.

对于使用将"随机"触发的进程组(即shell)的代码,此错误似乎是一个不可恢复的条件,使其更加可恶.我认为任何旨在达到理智水平的实现都会避免重新分配X为pid,而它仍然被用作pgid,但我无法在任何地方找到它.

Ulrich Drepper关于线程本地存储的论文概述了几种不同cpu架构的TLS ABI,但我发现它不足以作为实现TLS的基础,原因有两个:

1. 它省略了许多重要的拱门,如ARM,MIPS等(虽然包括一堆与Itanium完全无关的)
2. 更重要的是,它将大量实现细节与ABI混合在一起,因此很难说出互操作性需要哪些属性,哪些只是其实现的一部分.

例如,i386唯一的实际ABI要求是:

• %gs:0 指向指向自身的指针.
• 主可执行文件的TLS段(如果有)必须位于此地址的固定(通过链接器,负)偏移量.
• 初始加载的库的所有其他TLS段必须具有相对于此地址的运行时常量(即,对于每个线程相同,但在不同的程序运行中不一定相同)(并且动态链接器必须能够填充重定位)这些补偿).
• ___tls_get_addr并且__tls_get_addr函数必须以正确的语义存在,以便查找任意TLS段.

特别是,DTV的存在或布局不是 ABI的一部分,也不是主程序之外的TLS段的排序/布局.

似乎任何使用"TLS变体II"的拱门都具有大致上述ABI要求.但我完全不了解"TLS变体I"的要求,而且从阅读来源(在uClibc和glibc中)看来,甚至可能存在"变体I"的几种变体.

有没有更好的文件我应该看一下,或者熟悉TLS工作的人能向我解释ABI的要求吗？