soul.stone
探索云世界
soul.stone
Linux架构方面专家
我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
the first blog
http://network.51cto.com/art/201412/460623.htm
相关链接： http://openvswitch.org/ github: https://github.com/openvswitch/ovs/ https://www.sdnlab.com/tag/openvswitch/ http://blog.csdn.net/tantexian/article/details/46707175 ovs-vswitchd：OVS守护进程是OVS的核心部件，实现交换功能，和Linux内核兼容模块一起，实现基于流的交换（flow-based switching）。它和上层 controller 通信遵从 OPENFLOW 协议，它与 ovsdb-server 通信使用 OVSDB 协议，它和内核模块通过netlink通信，它支持多个独立的 datapath（网桥），它通过更改flow table 实现了绑定和VLAN等功能。 ovsdb-server：OVS轻量级的数据库服务器，用于整个OVS的配置信息，包括接口，交换内容，VLAN 等等。ovs-vswitchd 根据数据库中的配置信息工作。它于 manager 和 ovs-vswitchd 交换信息使用了OVSDB(JSON-RPC)的方式。 ovs-dpctl：一个工具，用来配置交换机内核模块，可以控制转发规则。 ovs-vsctl：主要是获取或者更改ovs-vswitchd的配置信息，此工具操作的时候会更新ovsdb-server中的数据库。 ovs-appctl：主要是向OVS守护进程发送命令的，一般用不上。 a utility that sends commands to running Open vSwitch daemons (ovs-vswitchd) ovsdbmonitor：GUI工具来显示ovsdb-server中数据信息。（Ubuntu下是可以使用apt-get安装，可以远程获取OVS数据库和OpenFlow的流表） ovs-controller：一个简单的OpenFlow控制器 ovs-ofctl：用来控制OVS作为OpenFlow交换机工作时候的流表内容。 ovs-pki：OpenFlow交换机创建和管理公钥框架； ovs-tcpundump：tcpdump的补丁，解析OpenFlow的消息； brocompat.ko : Linux bridge compatibility module openvswitch.ko : Open vSwitch switching datapath
website：https://frrouting.org/ github：https://github.com/FRRouting/frr FRRouting (FRR) is an IP routing protocol suite for Linux and Unix platforms which includes protocol daemons for BGP, IS-IS, LDP, OSPF, PIM, and RIP. FRR’s seamless integration with the native Linux/Unix IP networking stacks makes it applicable to a wide variety of use cases including connecting hosts/VMs/containers to the network, advertising network services, LAN switching and routing, Internet access routers, and Internet peering. 支持的协议列表： Protocol IPv4 IPv6OSPF OSPFv2 OSPFv3ISIS ISIS IPv4 ISIS IPv6RIP RIP RIPngBGP BGP IPv4 BGP IPv6BGP 4-byte AS BGP IPv4 4-byte AS BGP IPv6 4-byte ASLDP LDP IPv4 每个守护进程使用socket收发报文，以RIP为例： 1、static int rip_create(void) /* Create read and timer thread. */ rip_event(RIP_READ, rip->sock); rip_event(RIP_UPDATE_EVENT, 1); 2、void rip_event(enum rip_event event, int sock) thread_add_read(master, rip_read, NULL, sock, &rip->t_read); thread_add_timer(master, rip_update, NULL, sock ? 2 : rip->update_time + jitter, &rip->t_update); 3、static int rip_read(struct thread *t) len = recvfrom(sock, (char *)&rip_buf.buf, sizeof(rip_buf.buf), 0, (struct sockaddr *)&from, &fromlen); 4、static int rip_send_packet(u_char *buf, int size, struct sockaddr_in *to, struct connected *ifc) ret = sendto(rip->sock, buf, size, 0, (struct sockaddr *)&sin, sizeof(struct sockaddr_in));
github: https://github.com/Azure/SONiC 支持硬件列表：https://github.com/Azure/SONiC/wiki/Supported-Devices-and-Platforms 架构介绍：https://github.com/Azure/SONiC/wiki/Architecture Switch Hardware Switch hardware refers to all the physical components inside the network switch enclosure (chassis). This includes fans, power supplies, status LEDs and network transceivers. In SONiC terminology, these are called “system devices”. Switch Abstraction Interface (SAI) The switch abstraction interface is a standardized C API to the switching ASIC. This API is normally implemented by an SDK specific to the Switch ASIC. More information on SAI is available at the SAI GitHub repository. SAI Host Adapter The SAI Host Adapter’s role is to provide a mechanism for storing and synchronizing network switch data with the Switch ASIC. This includes initialization, configuration and current status of the switch ASIC. Network Applications Network applications, such as a BGP routing protocol, use the Object Libraries API’s to get and set the state of the SONiC SAI Host Adapter.
相关链接： https://www.sdnlab.com/tag/onos/ https://github.com/opennetworkinglab/onos https://en.wikipedia.org/wiki/ONOS
https://github.com/facebook/fboss
www.opennetworking.org 开放网络基金会（英语：Open Networking Foundation，缩写ONF）是一个非营利性的产业联盟，成员包括德国电信、Facebook、Google、微软、威讯通信和雅虎。其宗旨在于推动软件定义网络（SDN）和规范OpenFlow协议与相关技术，以促进互联网的进步。[2]该标准制定和SDN促进组织将使计算机与网络之间的云计算模糊化。[3]该计划旨在通过电信网络、无线网络、数据中心和其他网络领域中的简单软件更改来加速创新。[4] 截至2013年12月31日，该组织有123个公司成员。截至2014年6月，开放网络基金会已发展到150多家公司成员，其中包括24家软件定义网络的初创公司。[5]公司成员包括网络设备供应商、半导体公司、计算机公司、软件公司、电信服务运营商、超大规模数据中心运营商，以及企业用户。 在2016年，ONF宣布[6]打算与开放网络实验室（ON.Lab）合并。所产生的实体将保留ONF名称，两个非营利组织的合并预计将在2017年完成。 主要项目： 1、openflow规格定义 2、ONOS 3、CORD 4、mininet
http://www.opencompute.org/ 项目列表： 3、HARDWARE Management OpenBMC - framework & processes to contribute code, manage source tree & check-in process, oversee build tools and utilities. Rack Management Controllers- Rack level management solutions (HW, SW, API) and technologies. Review, recommend, collaborate on RM contributions DMTF Redfish API - review & adopt initial “OCP profile” Provide uniform management of firmware, alerting of hardware events and remote hardware access. Our focus will be on process automation and scalability by leveraging existing open standards whenever possible. We will coordinate with other groups within the OCP foundation to drive efforts. Provide a required process for submitting specifications to other workgroups that include a specification for hardware mgmt. The hardware management group will provide a template containing a recommended set or actions and events. 4、HPC HPC Project Scope: • Low latency top of rack switching • Combined Switch and micro servers • Combined compute and switching • Low latency scalable storage • Connectivity from HPC Fabrics/clustering technology to out of cluster networking via ethernet • OCP mechanicals (19 and 21 inch) • APIs and software interfaces • Open Hardware compute and switching Development of OCP HPC Interconnect silicon spec (can build on existing mainstream technologies such as PCIe, RapidIO, Infiniband, Ethernet) 5、NETWORKING Campus Branch Wireless (CBW) Open Network Install Environment (ONIE) Open Network Linux (ONL) SONIC Switch Abstraction Interface (SAI)
todo
http://dy.163.com/v2/article/detail/CDG9CD7G05179LAH.html 2月2日，SDxCentral发布了2017下一代数据中心研究报告(2017 Next Gen Data Center Networking Report)。这份报告系统介绍了下一代数据中心网络的发展趋势、关键功能、典型案例、行业标准以及热门产品。 下一代数据中心演进的四大驱动力 1、业务竞争驱动：企业提升自身竞争力，对敏捷性、差异化和成本节约提出了新要求 Increased Competitiveness Driving Agility, Cost-savings, Differentiation in IT 2、内容流量驱动： 高速增长的视频和富媒体内容成为数据中心的新压力 Increased Consumption of Video and Media-rich Content 3、交付模式驱动： 云计算和移动化成为主流交付模式 Dominance of Cloud and Mobile Applications 4、工作负载驱动： 大数据分析和物联网日益重要，未来将成为数字化转型的关键手段。 Importance of Data - Big Data, IoT and Analytics 这部分开场白都是套话，没什么干货，就不详细翻译了 下一代数据中心对网络的关键需求 1、简单化、标准化和模块化 Simplification, Standardization and Modularity 数据中心运营者希望能够删减那些不必要的路由/交换功能，利用标准服务器提供网络优化，采用较少商用芯片数量构建更为简单的网络矩阵，同时将L4-L7的功能迁移到标准服务器上，这些需求，都与传统厂商的理念背道而驰。 LinkedIn、Facebook、Microsoft、Google等巨头已经开启模块化数据中心Pod之路，每个Pod都包含了标准化的网络架构，大规模利用成本低廉的商品化交换机，芯片也切换到BCM、Marvell和一些新兴芯片制造商(比如Barefoot、Cavium Xpliant和盛科)。 模块化的节点更易部署和替换，也提升了横向扩展能力，随着这种云服务商的带动，大型企业级市场也有这种趋势。 2、对虚拟化和容器的支持 Virtualization and Containers 在虚拟化和容器化盛行的时代，无论南北流量还是东西流量，都无法回避虚拟交换机的存在。人们希望虚拟交换机的支持，能像以前使用VLAN一样简单。 复杂的叠加网络环境造成各种标签混杂，比如来自与广域网的MPLS链接很有可能就被ToR交换机给终结掉了。 3、可编程能力 Programmability 为满足业务敏捷型和灵活性需求，网络可编程能力必不可少。上层业务必须能够实时控制底层网络，进行编排和优化。无论这些业务采用基于XML/JSON的RESTful接口，还是用P4编程或者Openflow协议控制，都需要网络设备本身能够“被集成”，与数据中心融为一体。 如今已经有越来越多的企业级网络产品可以被云管理平台(比如Openstack、VMware vRealize suite、Cloudstack)集成部署。网络被系统配置管理是大势所趋，甚至这种响应被要求是实时的。 4、自动化和DevOps/NetOps Automation and DevOps/NetOps 可编程性让网络集成到编排系统成为可能，但是系统需要被部署、被监控、被更新，并非一劳永逸。传统情况下，网工最爱命令行CLIs，很多厂商提供过图形配置界面，但是很少能广泛应用的，大量的设备还是被“命令行”管理着。 但是，DevOps正在对网络行业产生影响，或者说我们需要NetOps来拯救。基于自动化配置工具(Ansible/Puppet/Chef等)，网工们也可以像管理服务器一样去管理网络基础设施了。 5、可视化与Troubleshooting Improved Visibility and Troubleshooting 跨数据中心流量暴增以及Overlays的存在，让网络可视化变得尤为重要。可视化有理于快速定位网络延迟或者洞察流量突发。还需要具备对流量数据的收集和分析能力，用于排障、优化和安全防范，如果只有海量告警事件日志，那就只能抓瞎了。 另外，由于数据中心网络正在演进为基于ECMP的leaf-spine三层Fabric，保障所有数据的可达性非常关键，不要让“大象数据流”阻挡了“老鼠数据流”，“可视化”有助于让我们了解整个交换矩阵发生了什么，甚至细化到每个交换机端口的缓存利用率。 6、开放的硬件平台 Open Hardware Platforms 从成本和可配置性考虑，数据中心网络运营者越来越关注白盒或者其他开放硬件平台。有人相信，采用白盒，在硬件成本上可以节省30%-80%。由于这些白盒供应商同时也为品牌交换机厂商提供OEM/ODM服务，所以产品品质和可靠性不存在疑问。 时至今日，诸如EdgeCore等低成本白盒硬件供应商值得考虑，但你需要找到成熟的软件来支持。另外，像Dell、HPE和华为也提供白盒交换机，但是会提供他们自己的品牌软件，这种模式被称为“灰盒”(gray box)。 下一代数据中心网络演进 “老帮菜”数据中心网络长这样 由纯物理交换机/路由器组成，有主备或者双A设计，以南北流量为主。 “新生代”数据中心网络长这样 到了云时代，SDN和NFV参与进来，数据中心网络的边界定义被扩大，从服务器内部的虚拟网络到数据中心物理网络，再到数据中心互联网络。 在这样的数据中心里，四个关键组件必不可少： 虚拟交换机：满足服务器内部vm和容器的交换需求。 网络加速卡：智能网卡或加速器提供vSwitch卸载、安全以及存储加速 ToR与Leaf/Spine：两层Clos架构再次得到推广，架构开放，扩展性强。（虽然这种架构早在1950年代就已经在电话交换网中使用了），大量的商用套片和白盒被应用在Leaf和Spine交换机中，降低成本，解决厂商锁定。 数据中心互联(DCI)：数据中心基于交换机就可以完成直连，DCI互联模块被直接集成到数据中心交换机上，比如100Gbps DWDM。L2 over L3的隧道技术也得到推广应用，还有我们不得不提的SDWAN。 下一代数据中心网络关键趋势 趋势1、解耦与白盒 Disaggregation and White box 解耦的意义包含两层，第一层：控制平面与数据平面结构，这是SDN的范畴；第二层：网络硬件与软件解耦，这是白盒和ONIE的范畴。 白盒交换机采用的商用套片通常来自于Broadcom(目前主流芯片如Trident II, Trident II+, Tomahawk等等)，这类白盒基于ONIE标准提供一个交换机启动环境，最终用户可以选择安装交换机OS，如 Big Switch的ONL、Apstra的Apstra OS、Cumulus Linux等等。 为保证网络与数据中心集成和可编程性，这些OS还提供了相应接口，包括OF-DPA (OpenFlow Data Plane Abstraction)、OpenNSL (Open Network Switch Layer) 以及 SAI (Switch Abstraction Interface)。前两个接口标准主要绑定Broadcom，而SAI出身于OCP，支持多个厂商的芯片(Broadcom, Cavium, Mellanox, Centec、Barefoot)。 在交换机OS之上，还有诸多为交换机管理和转发功能定制的“插件”，比如开源三层路由代码Quagga和BIRD，以及Facebook出品的FBOSS、微软Azure出品的SNOiC，开放的世界很精彩。 解耦的白盒阵营与传统的交换机贵族Cisco、Arista、Junper、Brocade还有很长的博弈时间，但是我们看到，戴尔、HPE、华为已经开始销售开放网络平台（灰盒）。而新进玩家Cumulus、EdgeCore、Pica8和其他ODM厂商也在努力推动白盒产业。 在OCP的推动下，新供应商们正在给市场带来更具性价比、更高性能的硬件产品，而开源团体也会在软件上持续努力，用廉价的开放产品去替代企业级市场那些高价货！ 趋势2、虚拟化、Overlays和Openstack Virtualization, Overlays and OpenStack 虽然Facebook声明他们的业务并不需要Overlays和计算虚拟化，(他们的应用被设计运行的物理服务器上)，但是Amazon、Google和Microsoft却是虚拟化和容器化的重度使用者。 在重度虚拟化应用场景，vSwitch必须保持高性能（基于硬件加速、DPDK、FDiO VPP等等），同时还需要支持Overlay的终结，VXLAN应该作为架顶交换机(ToR)的必选项：实现Overlays流量可视化、在VM和物理机混合接入环境下提供VTEP能力等等。 对于下一代数据中心网络来说，另一个重要考量是支持以Openstack为代表的CMP(cloud management platform)平台，提供部署、监控、管理接口，对于企业级运行环境，还应该支持VM热迁移的集成接口。 趋势3、支持ECMP的两层Clos-Fabrics 2-stage Leaf-spine Clos-Fabrics with ECMP and Pods 现代数据中心已经从老式胖树架构进化到两级L3 Leaf-spine Clos矩阵，基于ECMP提供多路径流量分担。这种架构抛弃了大型的机箱式核心交换机，用简单的Leaf-spine交换机实现部署低成本、高灵活。连老牌厂商Cisco、Juniper、Arista也开始拥抱Leaf-Spine，积极在企业级数据中心市场进行鼓吹推广。 而在全球最大的一些数据中心里面，Clos结构的网络被打包在“Pod”里面，通过横向扩展满足Pod巨量的连接需求(参见下文Facebook的Altoona数据中心)。 然而leaf-spine架构也有不爽之处，首先Leaf和Spine之间需要大量的网络连接，线缆维护复杂，替换和新增spine的时候，工作量是巨大的。其次，基于L3技术，VLAN受到Leaf交换机的限制，导致VM移动性不佳，这就必须依赖VXLAN之类的Overlay技术去解决，会增大开销。 由于Leaf和Spine之间的海量连接，要进行监控和排错很难，微软在其Azure数据中心里，采用了一种全量ping测试，被称为PingMesh。PingMesh本质上讲是一种强力的在所有端点之间运行Ping测试的方式，可视化的去显示任意两个端点之间的连接状况。 PingMesh已经在微软数据中心运行多年，每天要产生超过两千亿次探测。 趋势4、软件定义网络、策略、意图 SDN, Policy and Intent 当今数据中心网络之复杂，仅靠人肉运维是不可能的，SDN作为自动化工具，流行起来顺理成章。大型数据中心(如Goole和微软)，无论内部还是外部，都有各种形态的SDN存在，Goolge的 B4广域网，就是SDN最典型的案例之一。 在以云计算为核心的生产环境中，传统手工作坊式的网络配置、参数修改如同杯水车薪，应用需要基于CMP来自动化部署系统、优化参数，每个应用都有不同的配置文件、需要特定的网络支持以满足时延、弹性等QoS要求。这些需求会被绑定成策略集，自动化完成下发和部署。 Cisco ACI就是一个策略化(Policy-based)处理网络的商用案例，同样，OpenDaylight和ONOS等SDN控制器的目标，也是在网络部署中提供可编程策略。 基于策略分发，让我们正在向“意图型”网络(intent-based networking)演进：只需要“告诉我你想得到什么”，而不是“告诉我具体怎么做”，剩下的，交给SDN去干。 也许这就是智能网络的未来状态，让你从繁复的具体配置工作中解脱出来！ 趋势5、大数据分析 Big Data and Analytics 下一代数据中心网络的典型应用场景是大数据分析，戏剧性的是，网络生成的数据流本身就是一个大数据用例。很多厂商和组织抓取这些数据，用于优化和潜在安全分析，初创公司Pluribus和Big Switch都在兜售他们的数据监控能力，而Cisco则推出了Tetration平台用于网络数据分析。 下一代数据中心网络成果和标准 1、互联网巨头们的实践 A 6-Pack of Wedge, Firehose, Watchtower, Pluto, Saturn, Jupiter, Altair, Olympus and more 引领数据中心变革的，是那些别无选择只能追求持续创新的互联网企业，Facebook、Google、微软、领英都在不断努力，他们内部的数据中心团队驱动着从架构、软件、硬件全方位演进。 Google Google的数据中心已经进化到第5代，从设计了却没用的“Firehose”，到“Watchtower”，再到"Pluto" 和"Saturn"，直到今天使用的 "Jupiter"，最新保密设计并未对外公开。Google希望实现一个完整的内置网络的云基础设施，作为一个单元来设计。其目标是打造超过10000台Server的超级集群，将资源利用率发挥到极致。 LinkedIn LinkedIn的网络团队对自己的Altair项目和Falco项目非常自豪。Falco项目其实是基于BCM Tomahawk芯片打造的交换机，该交换机被命名为“鸽子”，提供3.2Tbps交换能力，可以作为Leaf或者Spine使用。“鸽子”运行基于Linux的软件系统，并集成了一大宗监控和管理工具。Altair项目则是一个大规模可伸缩的数据中心网络Fabric，用于替换传统网络。 Facebook Facebook是开放计算硬件的领导者，他们发起了的OCP，并贡献了Wedge和6-pack。 Wedge是一款ToR交换机，有40G和100G两种规格，全部贡献给了OCP项目，并且目前两款硬件都可以从第三方供应商EdgeCore买到。 6-pack是Facebook发布的开放式模块化交换机平台，它以Wedge为基本构件，是一个全网状且无阻断的两级（two-stage）交换机，内含12个独立的交换组件，每个组件的交换容量为1.28Tbps。每个组件也运行自己的操作系统，从交换、主板控制，到冷却系统都是独立的。这代表用户能够在不影响整体系统或软/硬件的前提下更改系统的任何部份，并藉由独特的双背板解决方案来打造无阻断的拓扑结构。 在数据中心层面，Facebook设计了Pod级别的模块——Altoona。Altoona设计可借鉴之处在于，你可以使用小型开放交换机构建你的数据中心，这个架构可以让你扩展到任何规模，而不需要改变基本构建块。 Microsoft Azure 微软Azure的网络广泛使用了SDN技术，每个Azure节点都是用了基于FPGA的网络加速卡——Azure Smart NIC，用来加速流处理、存储进程、QoS以及加解密。Azure使用SDN控制每块加速卡上的流表和规则，保障Azure节点的高性能吞吐。 微软同时也在云交换机领域也在驱动创新，是SAI和SONiC(Software for Open Networking in the Cloud)的应用先锋。SONiC是一个网络软件组件集合，包含了交换机常备的BGP、ECMP、LLDP等功能，得到了大量硬件供应商的支持，这里面包括了Arista(微软是A公司最大的客户之一)、BigSwitch、Dell、Mellanox，以及芯片厂商BCM、Cavium和盛科。 2、Linux基金会及相关项目 Linux Foundation and its associated projects 项目很多，就不一一详述了，统一列在这里 3、OCP和TIP Open Compute Project (OCP) and Telecom Infra Project (TIP) 下一代数据中心网络最主要的推动者就是OCP，该项目由Facebook发起，目前获得了业内广泛的支持。从互联网巨头LinkedIn、 Microsoft、Google，到运营商AT&T、Fidelity和DT 再到设备商Cisco、Dell,、Huawei、HPE、Intel、 Ericsson等等。下图为OCP白金会员列表。 OCP是数据中心关键硬件方案之家，包括高密度机架(Open Rack)、服务器(Microsoft OpenCloudServer和Facebook Yosemite)、网络平台(Wedge 40 100 6-pack)。OCP还是ONIE、ONL、SAI、SONiC这些核心网络软件项目的老巢。 作为OCP的补充，Facebook在2016年又成立了TIP项目(Telecom Infra Project)，推动运营商基础设施的变革和演进，替换传统网络架构。TIP的成员包括Intel、Nokia、德电、SK电信、沃达丰、T-Mobile以及思科Juniper等。
https://opennetlinux.org/ github：https://github.com/OpenComputeProject/OpenNetworkLinux Open Network Linux is a Linux distribution for "bare metal" switches, that is, network forwarding devices built from commodity components. ONL uses ONIE to install onto on-board flash memory. Open Network Linux is a part of the Open Compute Project and is a component in a growing collection of open source and commercial projects. Open Network Linux supports multiple switch fabric APIs including: OF-DPA, OpenNSL and SAI. Specific information about hardware support for the different APIs can be found in the HCL （支持单板列表） Open Network Linux is compatible with most forwarding agents including: FRR, BIRD, Facebook FBOSS and Azure SONiC. Forwarding Agent Support ONL provides multiple options for forwarding agents and APIs to control forwarding on switches. The options go from direct (OpenNSL, SAI, OF-DPA) to simplistic ipv4 only (ORC) to complex full systems (FBOSS). Each option is available via installable packages. APIs OpenNSL Provides a Open abstraction interface to supported Broadcom chipsets and is supported by Accton on many of their platforms. OF-DPA is a OpenFlow focused API from Broadcom and is supported on most platforms. SAI is a fully open multi-vendor abstraction interface that runs on switching chipsets from Broadcom, Cavium, Mellanox and more. Routing and Switching Agents ONL Supports ORC (Open Route Cache) an IPv4 only netlink listener which provides logical interfaces for routing protocols such as Quagga, BIRD and others to run on. See the HCL for a list of supported platforms. ONL Supports the Facebook FBOSS fowarding agent. FBOSS currently only runs on the Wedge with other systems in the works. Accton/Edge-Core Device Ports CPU Forwarding ONL Ver Tested In Lab OF-DPA OpenNSL SAI Accton AS4600-54T 48x1G + 4x10G FreeScale P2020 BCM56540 (Apollo2) 2.0.0 dd42deb Yes Yes*** Yes*** No Accton AS4610-54P 48x1G + 4x10G + 2x20G Dual-core ARM Cortex A9 1GHz BCM56340 (Helix4) 2.0.0 fd18376 Yes No No No Accton AS5610-52X 48x10G + 4x40G FreeScale P2020 BCM56846 (Trident+) 2.0.0 1d7a4d8 Yes No No No Accton AS5710-54X 48x10G + 6x40G FreeScale P2041 BCM56854 (Trident2) 2.0.0 7a8dc98 Yes Yes*** Yes*** No Accton AS6700-32X 32x40G FreeScale P2041 BCM56850 (Trident2) 2.0.0 Yes No No No Accton AS5512-54X 48x10G + 6x40G Intel Rangeley C2538 x86 MediaTek/Nephos MT3258 2.0.0 dd42deb Yes No No No Accton AS5712-54X 48x10G + 6x40G Intel Rangeley C2538 x86 BCM56854 (Trident2) 2.0.0 1d7a4d8 Yes Yes*** Yes*** No Accton AS6712-32X 32x40G Intel Rangeley C2538 x86 BCM56850 (Trident2) 2.0.0 Yes Yes*** Yes*** No Accton AS5812-54T 48x10G + 6x40G Intel Rangeley C2538 x86 BCM56864 (Trident2+) 2.0.0 Yes No No No Accton AS5812-54X 48x10G + 6x40G Intel Rangeley C2538 x86 BCM56864 (Trident2+) 2.0.0 Yes Yes*** Yes*** No Accton AS6812-32X 32x40G Intel Rangeley C2538 x86 BCM56864 (Trident2+) 2.0.0 Yes Yes*** Yes*** No Accton AS7712-32X 32x100G Intel Rangeley C2538 x86 BCM56960 (Tomahawk) 2.0.0 84df541 Yes Yes*** Yes*** No Accton AS7716-32X 32x100G Intel Xeon D-1518 x86 BCM56960 (Tomahawk) 2.0.0 Yes Yes*** Yes*** No Accton Wedge-16X 16x40G Intel Rangeley C2550 x86 BCM56864 (Trident2+) WIP** Yes No Yes No Accton (FB) Wedge 100 32x100G Intel Bay Trail E3845 x86 BCM56960 (Tomahawk) WIP** Yes No Yes No
https://github.com/FRRouting/frr/wiki/Building-FRR-on-Ubuntu-1404 Install required packages Add packages: apt-get install git autoconf automake libtool make gawk libreadline-dev \ texinfo dejagnu pkg-config libpam0g-dev libjson-c-dev bison flex \ python-pytest libc-ares-dev python3-dev Add frr groups and user sudo groupadd -g 92 frr sudo groupadd -r -g 85 frrvty sudo adduser --system --ingroup frr --home /var/run/frr/ \ --gecos "FRR suite" --shell /sbin/nologin frr sudo usermod -a -G frrvty frr Download Source, configure and compile it (You may prefer different options on configure statement. These are just an example.) git clone https://github.com/frrouting/frr.git frr cd frr ./bootstrap.sh ./configure \ --prefix=/usr \ --enable-exampledir=/usr/share/doc/frr/examples/ \ --localstatedir=/var/run/frr \ --sbindir=/usr/lib/frr \ --sysconfdir=/etc/frr \ --enable-pimd \ --enable-watchfrr \ --enable-ospfclient=yes \ --enable-ospfapi=yes \ --enable-multipath=64 \ --enable-user=frr \ --enable-group=frr \ --enable-vty-group=frrvty \ --enable-configfile-mask=0640 \ --enable-logfile-mask=0640 \ --enable-rtadv \ --enable-fpm \ --enable-ldpd \ --with-pkg-git-version \ --with-pkg-extra-version=-MyOwnFRRVersion make make check sudo make install derek@kbox:~/share/frr$ autoreconf -i.ibtoolize: error: AC_CONFIG_MACRO_DIRS([m4]) conflicts with ACLOCAL_AMFLAGS=-I m4autoreconf: libtoolize failed with exit status: 1 在项目的根目录下添加如下.gitattributes文件便可 *.sh -crlf *.ac -crlf *.am -crlf Create empty FRR configuration files sudo install -m 755 -o frr -g frr -d /var/log/frr sudo install -m 775 -o frr -g frrvty -d /etc/frr sudo install -m 640 -o frr -g frr /dev/null /etc/frr/zebra.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/bgpd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/ospfd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/ospf6d.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/isisd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/ripd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/ripngd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/pimd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/ldpd.conf sudo install -m 640 -o frr -g frr /dev/null /etc/frr/nhrpd.conf sudo install -m 640 -o frr -g frrvty /dev/null /etc/frr/vtysh.conf nable IP & IPv6 forwarding Edit /etc/sysctl.conf and uncomment the following values (ignore the other settings) # Uncomment the next line to enable packet forwarding for IPv4 net.ipv4.ip_forward=1 # Uncomment the next line to enable packet forwarding for IPv6 # Enabling this option disables Stateless Address Autoconfiguration # based on Router Advertisements for this host net.ipv6.conf.all.forwarding=1 Reboot or use sysctl -p to apply the same config to the running system ### Install the init.d service sudo install -m 755 tools/frr /etc/init.d/frr sudo install -m 644 tools/etc/frr/daemons /etc/frr/daemons sudo install -m 644 tools/etc/frr/daemons.conf /etc/frr/daemons.conf sudo install -m 644 -o frr -g frr tools/etc/frr/vtysh.conf /etc/frr/vtysh.conf Enable daemons Edit /etc/frr/daemons and change the value from "no" to "yes" for those daemons you want to start by systemd. For example. zebra=yes bgpd=yes ospfd=yes ospf6d=yes ripd=yes ripngd=yes isisd=yes Start the init.d service sudo /etc/init.d/frr start use /etc/init.d/frr status to check its status. vtysh sudo vtysh derek@kbox:~$ sudo vtysh [sudo] password for derek: Hello, this is FRRouting (version 3.1-dev-MyOwnFRRVersion-gff9eb72). Copyright 1996-2005 Kunihiro Ishiguro, et al. This is a git build of frr-3.1-dev-699-g4ff9eb72 Associated branch(es): local:master github/frrouting/frr.git/master kbox# show version FRRouting 3.1-dev-MyOwnFRRVersion-gff9eb72 (kbox). Copyright 1996-2005 Kunihiro Ishiguro, et al. This is a git build of frr-3.1-dev-699-g4ff9eb72 Associated branch(es): local:master github/frrouting/frr.git/master configured with: '--prefix=/usr' '--enable-exampledir=/usr/share/doc/frr/examples/' '--localstatedir=/var/run/frr' '--sbindir=/usr/lib/frr'...
1、fand 1）main函数 read_sysfs_int("/sys/bus/i2c/drivers/cmmcpld/13-003e/slotid", &sysfs_value) write_fan_speed(fan + fan_offset, fan_speed) write_fan_led(fan + fan_offset, FAN_LED_BLUE) start_watchdog(0) while(1){ critical_temp = read_critical_max_temp(); alarm_temp = read_alarm_max_temp(); raising_pwm = calculate_raising_fan_pwm(critical_temp); falling_pwm = calculate_falling_fan_pwm(critical_temp); write_fan_led(fan + fan_offset, FAN_LED_RED); } 2）write_fan_speed int write_fan_speed(const int fan, const int value) {int unit = value * PWM_UNIT_MAX / 100; if (unit == PWM_UNIT_MAX) unit--; return galaxy100_set_fan_sysfs(fan, unit);} 3）galaxy100_set_fan_sysfs info = &galaxy100_fantray_info[fan]; channel = &info->channel_info; snprintf(fullpath, PATH_CACHE_SIZE, "%s/%s", channel->prefix, "fantray1_pwm");ret = write_sysfs_int(fullpath, value); snprintf(fullpath, PATH_CACHE_SIZE, "%s/%s", channel->prefix, "fantray2_pwm");ret = write_sysfs_int(fullpath, value); snprintf(fullpath, PATH_CACHE_SIZE, "%s/%s", channel->prefix, "fantray3_pwm");ret = write_sysfs_int(fullpath, value); 4) write_sysfs_int int write_sysfs_int(char *sysfs_path, int buffer){ int rc = 0; char writeBuf[PATH_CACHE_SIZE]; snprintf(writeBuf, PATH_CACHE_SIZE, "%d", buffer); return write_sysfs_raw(sysfs_path, writeBuf);} int write_sysfs_raw_internal(const char *device, char *value, int log) fp = fopen(device, "w"); rc = fputs(value, fp); fclose(fp); 5) fancpld_attr_table typedef struct i2c_dev_attr_st_ { const char *ida_name; const char *ida_help; i2c_dev_attr_show_fn ida_show; i2c_dev_attr_store_fn ida_store; int ida_reg; int ida_bit_offset; int ida_n_bits; } i2c_dev_attr_st; const i2c_dev_attr_st fancpld_attr_table[] = { { "fantray1_pwm", FANTRAY_PWM_HELP, I2C_DEV_ATTR_SHOW_DEFAULT, I2C_DEV_ATTR_STORE_DEFAULT, 0x20, 0, 5, }, } static int fancpld_probe(struct i2c_client *client, const struct i2c_device_id *id){ int n_attrs = sizeof(fancpld_attr_table) / sizeof(fancpld_attr_table[0]); return i2c_dev_sysfs_data_init(client, &fancpld_data, fancpld_attr_table, n_attrs);} static struct i2c_driver fancpld_driver = { .class = I2C_CLASS_HWMON, .driver = { .name = "fancpld", }, .probe = fancpld_probe, .remove = fancpld_remove, .id_table = fancpld_id, .detect = fancpld_detect, .address_list = normal_i2c,}; static int __init fancpld_mod_init(void){ return i2c_add_driver(&fancpld_driver);} 6) i2c_dev_sysfs_store static ssize_t i2c_dev_sysfs_store(struct device *dev, struct device_attribute *attr, const char *buf, size_t count) if (dev_attr->ida_store != I2C_DEV_ATTR_STORE_DEFAULT) { return dev_attr->ida_store(dev, attr, buf, count); } /* default handling, first read back the current value */ val = i2c_smbus_read_byte_data(client, dev_attr->ida_reg); /* mask out all bits for the value requested */ val &= ~(req_val_mask << dev_attr->ida_bit_offset); val |= req_val << dev_attr->ida_bit_offset; val = i2c_smbus_write_byte_data(client, dev_attr->ida_reg, val); 7）module_init Cmmcpld.c (meta-facebook\meta-cmm\recipes-kernel\cpld-mod\files):module_init(cmmcpld_mod_init); Com_e_driver.c (meta-facebook\meta-wedge100\recipes-kernel\com-e-mod\files):module_init(com_e_mod_init); Fancpld.c (meta-facebook\meta-cmm\recipes-kernel\cpld-mod\files):module_init(fancpld_mod_init); Fancpld.c (meta-facebook\meta-wedge100\recipes-kernel\cpld-mod\files):module_init(fancpld_mod_init); Fb_panther_plus.c (meta-facebook\meta-wedge\recipes-kernel\fb-panther-mod\files):module_init(sensors_panther_plus_init); Galaxy100_ec.c (meta-facebook\meta-galaxy100\recipes-kernel\i2c-mode\files):module_init(ec_mod_init); Ir358x.c (meta-facebook\meta-galaxy100\recipes-kernel\i2c-mode\files):module_init(ir358x_mod_init); Pwr1014a.c (meta-facebook\meta-galaxy100\recipes-kernel\i2c-mode\files):module_init(pwr1014a_mod_init); Scmcpld.c (meta-facebook\meta-galaxy100\recipes-kernel\cpld-mod\files):module_init(scmcpld_mod_init); Syscpld.c (meta-facebook\meta-galaxy100\recipes-kernel\cpld-mod\files):module_init(syscpld_mod_init); Syscpld.c (meta-facebook\meta-wedge100\recipes-kernel\cpld-mod\files):module_init(syscpld_mod_init); 每个文件对应某个单板的一个设备驱动，每个设备驱动定义一个i2c_dev_attr_st数组，支持用户态通过文件方式进行读写访问。 2、lib_ipmb_handle 1）int pal_read_cpu_temp(uint8_t snr_num, float *value) req->cmd = CMD_NM_SEND_RAW_PECI; lib_ipmb_handle(bus_id, tbuf, tlen+1, rbuf1, &rlen); 2) bic_set_gpio(uint8_t slot_id, uint8_t gpio, uint8_t value) bic_ipmb_wrapper(slot_id, NETFN_OEM_1S_REQ, CMD_OEM_1S_SET_GPIO, tbuf, 11, rbuf, &rlen) get_ipmb_bus_id(slot_id) lib_ipmb_handle(bus_id, tbuf, tlen, &rbuf, &rlen) // copy the received data back to caller *rxlen = rlen - IPMB_HDR_SIZE - IPMI_RESP_HDR_SIZE; memcpy(rxbuf, res->data, *rxlen); 3) void lib_ipmb_handle(unsigned char bus_id, unsigned char *request, unsigned char req_len, unsigned char *response, unsigned char *res_len) sprintf(sock_path, "%s_%d", SOCK_PATH_IPMB, bus_id); //#define SOCK_PATH_IPMB "/tmp/ipmb_socket" s = socket(AF_UNIX, SOCK_STREAM, 0) connect(s, (struct sockaddr *)&remote, len) send(s, request, req_len, 0) recv(s, response, MAX_IPMB_RES_LEN, 0)
1、void openlog(const char *ident, int option, int facility); 第一个参数ident将是一个标记，ident所表示的字符串将固定地加在每行日志的前面以标识这个日志，通常就写成当前程序的名称以作标记。第二个参数option是下列值取与运算的结果：LOG_CONS，LOG_NDELAY， LOG_NOWAIT， LOG_ODELAY， LOG_PERROR，LOG_PID，各值意义请参考man openlog手册： LOG_CONS Writedirectly to system console if there is an error while sending tosystem logger. LOG_NDELAY Openthe connection immediately (normally, the connection is opened whenthe first message is logged). LOG_NOWAIT Don’t wait for childprocesses that may have been created while logging themessage. (The GNU C library does not createa child process, so this option has no effect onLinux.) LOG_ODELAY The converseof LOG_NDELAY; opening of the connection is delayed until syslog()is called. (This is the default, and need not be specified.) LOG_PERROR (Notin SUSv3.) Print to stderr as well. LOG_PID IncludePID with each message. 第三个参数facility指明记录日志的程序的类型。 The facility argument is used to specify what type ofprogram is logging the message. This lets the configuration file specify thatmessages from different facilities will be handled differently. LOG_AUTH security/authorization messages (DEPRECATED Use LOG_AUTHPRIVinstead) LOG_AUTHPRIV security/authorization messages (private) LOG_CRON clock daemon (cron and at) LOG_DAEMON system daemons without separate facility value LOG_FTP ftp daemon LOG_KERN kernel messages (these can't be generage from user processes) LOG_LOCAL0 through LOG_LOCAL7 reserved for local use LOG_LPR line printer subsystem LOG_MAIL mail subsystem LOG_NEWS USENET news subsystem LOG_SYSLOG messages generated internally by syslogd(8) LOG_USER (default) generic user-level messages LOG_UUCP UUCP subsystem 2、void syslog(int priority, const char *format, ...); This determines the importance of the message. The levels are, in order of decreasing importance: LOG_EMERG system is unusable LOG_ALERT action must be taken immediately LOG_CRIT critical conditions LOG_ERR error conditions LOG_WARNING warning conditions LOG_NOTICE normal, but significant, condition LOG_INFO informational message LOG_DEBUG debug-level message The function setlogmask(3) can be used to restrict logging tospecified levels only. 3、int setlogmask(int maskpri); 进程有一个日志优先级掩码，该掩码决定哪些调用syslog(3)可能被记录。所有其他调用都将被忽略。日志是为在掩码中设置相应位的优先级启用的。最初的掩码是这样的，日志是为所有优先级启用的。 setlogmask()函数为当前的进程设置这个日志掩码，并返回先前的掩码。如果掩码参数为0，那么当前的日志掩码不会被修改。 这8个优先级分别是LOG_EMERG, LOG_ALERT, LOG_CRIT, LOG_ERR, LOG_WARNING, LOG_NOTICE, LOG_INFO and LOG_DEBUG.与优先级p相对应的位是LOG_MASK(p)。一些系统还提供了一个宏LOG_UPTO(p)，以在上面的列表中包括p的所有优先级。 4、调用openlog是可选择的。如果不调用openlog，则在第一次调用syslog时，自动调用openlog。调用closelog也是可选择的，它只是关闭被用于与syslog守护进程通信的描述符。调用openlog使我们可以指定一个ident，以后， 此ident 将被加至每则记录消息中。 5、代码示例 #include <syslog.h> int main(int argc, char **argv) { openlog("MyMsgMARK", LOG_CONS | LOG_PID, 0); syslog(LOG_DEBUG, "This is a syslog test message generated by program '%s'\n", argv[0]); closelog(); return0; } 编译生成可执行程序后，运行一次程序将向/var/log/message文件添加一行信息如下： Feb 12 08:48:38 localhost MyMsgMARK[7085]: This is a syslog testmessage generated by program './a.out'
https://github.com/Broadcom-Switch/OpenNSL Open Network Switch Layer (OpenNSL) is a library of network switch APIs that is openly available for programming Broadcom network switch silicon based platforms. These open APIs enable development of networking application software based on Broadcom network switch architecture based platforms. Open Network Switch Library (OpenNSL) is a library of Open Networking APIs that enable the development of innovative open source networking projects on widely deployed Broadcom network switch-based systems. It allows developers to customize, enhance, and deliver differentiated solutions, leveraging the capabilities of the feature-rich and industry-leading StrataXGS® architecture.With the OpenNSL software platform, Broadcom is publishing APIs that map Broadcom's Software Development Kit (SDK) to an open, north-bound interface, enabling the integration of new applications and creating the ability to optimize switch hardware platforms. This gives users the freedom to control their technology, share their designs, and boost application innovation. Examples include network monitoring, load balancing, service chaining, workload optimization, and traffic engineering.OpenNSL software is available in two packages:• An OEM and ODM Development Package (ODP), which is a full-source code package distributed under the Broadcom SLA.• A Community Development Package (CDP), which is an Open API library with Application Development Kit distributed on GitHub. FEATURES• Rich set of APIs for most commonly used switching and routing functions are as follows:– L2/L3/VLAN management.– Port and switch management.– Link monitoring and error handling.– Packet transmit and receive.– Trunking.– Buffer Statistics Tracking.– Packet Tracing and Injection.• Portable across StrataXGS® architecture today and StrataDNX™ in the future.• Supported by growing number of OEM and ODM partners. SUPPORTED OPEN PROJECTSOpenNSL is used in multiple open projects driven by the community. A partial list of these projects is given below:• FBOSS: OpenNSL provides foundational technology that allows the Facebook Open Switching System (FBOSS) to be open.• Open Network Linux: A Linux distribution for bare metal switches that includes OpenNSL.• BroadView: A software suite that provides programmable access to the internals of a switch in a fast and scalable manner.• Open L3 Routing: NTT has developed a pluggable L3 routing agent built on OpenNSL that was demonstrated at the OCP workshop in Oct 2015.• OpenSwitch: New open source, Linux based fully featured L2/L3 Network Operating System (NOS) platform. All the current OpenSwitch platforms are Broadcom based and built on top of OpenNSL. ### API Overview Buffer Statistics Tracking (BST) Class of Service Queue Configuration Error Handling APIs Field Processor APIs Initialization APIs Kernel Network (KNET) Configuration Layer 2 Address Management Layer 3 Management Link Monitoring and Notification Port Mirroring APIs Multicast Management APIs Packet Trace Policer configuration APIs Port Configuration QoS Statistics Spanning Tree Groups Switch Control APIs Trunking Tunneling Packet Transmit and Receive VLAN Configuration Virtual Switching Instance Vxlan Warm Boot
todo
1、SONiC/FBOSS/OpenSwitch/ONL/Cumulus都属性网络操作系统，SONiC和FBOSS(以及snaproute)一样强调是网络软件集合，而非Linux发行版本，可以看作app级NOS；ONL和Cumulus则强调做Linux的发行版本（网络操作系统类），OpenSwitch使用Yocto构建内核和基础文件系统，所以它也算是Linux的发行版本。 2、什么是Linux发行版本，就是内核+文件系统+工具集+应用软件包（仓库），各发行版本之间内核的差异应该是最小的，基本都是基于Linux内核的某个发行版本，文件系统遵循FHS规范 3、NOS的主要功能 NOS的基础服务：配置管理（CLI、netconf、Jason、SNMP等）、系统管理（诊断维护、补丁管理、进程监控、时间管理等）、设备管理（整机管理、设备管理、时钟管理、固件管理、电子标签、故障管理、能力管理、License）、信息中心（Log\告警）、数据库（订阅/发布机制、系统配置信息、系统状态信息、统计信息、可编程API等）、虚拟化（KVM\DOCKER\LXC\libvirt）网络应用：传统网络业务（如quagga\XORP实现的二三层业务）和SDN网络业务（Openflow\OVS） //网络应用的协议收发包机制：socket（netlink？）或pcap。应用：网络自动化等应用，如puppet、chef、ansible 4、BCM贡献了OpenNSL和BroadView
https://www.broadcom.com/products/ethernet-connectivity/software/of-dpa http://broadcom-switch.github.io/of-dpa/doc/html/OFDPA_OVERVIEW.html OpenFlow Data Plane Abstraction (OF-DPA) is an application software component that implements an adaptation layer between OpenFlow and the Broadcom Silicon SDK. OF-DPA enables scalable implementation of OpenFlow 1.3 on Broadcom switch devices. Figure 1 shows the OF-DPA software component and its relation to other OpenFlow system components. OF-DPA software is available in two packages: An OEM & ODM Development Package (ODP), which is a full source code package distributed under Broadcom SLA. A Community Development Package (CDP), which is an Open API library with Application Development Kit distributed on GitHub. API: http://broadcom-switch.github.io/of-dpa/doc/html/group__GLOFDPAAPI.html API Layer: Provides the northbound OF-DPA APIs. These are available via RPC in the inter-process mode or as direct function calls to a user application that links with the OF-DPA libraries. OF-DPA does not have a user interface (e.g. a CLI). All control is done via APIs. All APIs calls are synchronous and control is returned to the caller after changes are committed to the hardware. OFDB Layer: This is the OF-DPA database layer. OFDB is the software database for the flow, group and port tables. It provides APIs to manage these tables. OFDB APIs are invoked by the following layers of OF-DPA: API: OFDB stores the management state of the system. OFDB APIs are invoked by the API layer for configuration updates like flow addition, deletion, etc. Mapping: OFDB also stores system status information like port link status, etc. The mapping layer receives these port state updates from the hardware and invokes OFDB APIs to update the port tables in the database. Datapath: The datapath layer invokes OFDB APIs to traverse through flow tables etc. and perform housekeeping operations like flow aging. Datapath Layer: Implements a task that wakes up periodically and traverses flow tables to perform flow aging operations. On detecting aged flows, it sends event notifications to client applications. Mapping/Driver Layer: Provides system mapping and driver functions. All system initialization is done here. The driver, OFDB, and datapath layers are initialized during system startup. Functions to retrieve system specific information like table sizes, valid VLANs, etc. are implemented in this layer. The driver functions provide an abstraction layer over the Broadcom SDK. These functions are invoked to program and query the hardware. The driver layer defines the interface OF-DPA requires when ported to other platforms. Platform Layer: Provides platform specific initialization structures and functions. These functions are invoked during system startup.
wiki：https://en.wikipedia.org/wiki/COM_Express COM Express, a computer-on-module (COM) form factor, is a highly integrated and compact PC that can be used in a design application much like an integrated circuit component. Each COM Express Module COM integrates core CPUand memory functionality, the common I/O of a PC/AT, USB, audio, graphics (PEG), and Ethernet. All I/O signals are mapped to two high density, low profile connectors on the bottom side of the module. COM Express employs a mezzanine-based approach. The COM modules plug into a baseboard that is typically customized to the application. Over time, the COM Express mezzanine modules can be upgraded to newer, backwards-compatible versions. COM Express is commonly used in Industrial, Military/Aerospace, Gaming, Medical, Transportation, IoT, and General Computing embedded applications. The COM Express specification is hosted by PICMG. It is not freely available but a paper copy may be purchased for $150USD from the PICMG website. The current revision 3.0 (PICMG COM.0 R3.0) was released in March 2017. The original revision 1.0 was released July 10, 2005. 相关： ETX XTX ESMexpress Qseven SMARC EOMA-68
https://www.bigswitch.com/ https://www.sdnlab.com/18350.html //todo BigSwitch可以说是根正苗红的SDN玩家，公司从2010年成立，公司的主要创始人有很多都是从Clean State项目组出身的，包括Guido Appenzeller和Rob Sherwood，和Martin Cassado属于同一拨选手。几人都是OpenFlow的骨灰级玩家，不过BigSwitch和Nicira走的路线却有着很大的差异，BigSwitch用OpenFlow做的是Underlay，数据平面上搞得是白盒的OS，而Nicira用OpenFlow做的是Overlay，数据平面上搞的是Hypervisor上的vswitch。两者相比较而言，Bigswitch的理念是纯OpenFlow来做数据中心，偏向于狭义范畴的SDN，而Nicira走的理念则更接地气一点，Overlay一提出来对了很多人的胃口。随着Vmware的天价收购，Nicira成为了SDN界最知名的大明星，而BigSwitch至今仍然独立地存在着。 BigSwitch为OpenFlow贡献了非常多的知名的开源项目，控制器有FloodLight，协议编译工具Loxigen，虚拟化中间件FlowVisor，交换机代理Indigo，以及测试工具OFLOPS等等，这些开源项目（尤其是Floodlight）奠定了BigSwitch在开源SDN生态圈中的重要地位。OpenDaylight在成立之初，BigSwitch作为白金会员希望把自己的控制器代码作为OpenDaylight控制器的核心，不过社区最后采纳了将BigSwitch和Cisco One控制器进行融合的方案，以提供对OpenFlow在内的多种南向协议的支持。“提供多种南向协议的支持”听起来很美好，背后实际上是Cisco对当时火热的OpenFlow的围剿，眼看着社区ODL社区与OpenFlow背道而驰，BigSwitch在社区仅成立两个月后就立即选择了退出。不过，在Cisco的强大号召下，OpenDaylight还是建立起了广泛的生态，一定程度上可以说是成功地给OpenFlow降了温。 市场策略上，BigSwitch把基于Indigo的交换机操作系统Switch Light也贡献了出来，并和Accton等ODM厂商共同推广OpenFlow交换机。这种交换机出厂时没有操作系统，启动会自动到BigSwitch控制器上去下载Switch Light，BigSwitch将自己的这种模式定义为“BriteBox”。“Brite”是“Brand-White”的缩写，BigSwitch的商业逻辑是通过自己的开源交换机OS来捆绑白盒，从而销售自己的OpenFlow控制器。 当然ONL只是一个通用的OS，Switch OS厂商需要基于ONL来提供他们自己的OS，如Pic8、Cumulus、Pluribus等等。Switch Light是BigSwitch提供的基于ONL的OS，其定制化的内容就在于Indigo，即为本小节第一张图中橙红色的部分。Indigo是BigSwitch开源出来的一个OpenFlow Agent，下图是其Indigo_v2内部模块的简单示意。Indigo北向是OpenFlow控制器（图中为BigSwitch开源的FloodLight），LoxiGen（同为BigSwitch开源）为其提供OpenFlow 协议的编码。南向是转发通道的SDK。如果是转发是ASIC，那么Switch Light经过包装后就变成了白盒交换机，如果转发是Linux Kernel，那么Switch Light包装后就是虚拟交换机IVS（同为BigSwitch开源）。Switch Light不是OpenFlow传统意义上的“Thin Agent”，Switch Light在Indigo之外还增加了很多本地功能，如DHCP、ARP、LLDP、LACP、ICMP等等，能够有效地防止这些流量对Controller的冲击，以增强Controller的可靠性。下图示意了IVS相比于标准的OpenvSwitch增加的部分功能。
https://frrouting.org/ github：https://github.com/FRRouting/frr FRRouting (FRR) is an IP routing protocol suite for Linux and Unix platforms which includes protocol daemons for BGP, IS-IS, LDP, OSPF, PIM, and RIP. FRR’s seamless integration with the native Linux/Unix IP networking stacks makes it applicable to a wide variety of use cases including connecting hosts/VMs/containers to the network, advertising network services, LAN switching and routing, Internet access routers, and Internet peering. FRR has its roots in the Quagga project. In fact, it was started by many long-time Quagga developers who combined their efforts to improve on Quagga's well-established foundation in order to create the best routing protocol stack available. We invite you to participate in the FRRouting community and help shape the future of networking.
官网：https://p4.org/ github：https://github.com/p4lang/tutorials 相关文章： P4语言编程快速开始：https://www.sdnlab.com/18072.html 用P4对数据平面进行编程：https://www.sdnlab.com/17456.html
网址：http://www.cavium.com/xpliant-ethernet-switch-product-family.html The XPliant® CNX880XX family of Ethernet switches provide unprecedented flexibility in protocol processing without compromising speed. XPliant Packet Architecture (XPA™) allows programming of every element of switch packet processing. Cavium™ / XPliant provides a complete set of networking protocols with the switch. However, as new protocols are required, the switch can be updated by software to add support for these new protocols, including changes to parsing, lookups, traffic scheduling, packet modification, scheduling, and traffic monitoring. The CNX880XX with XPA is the first switch that can do this – and it provides industry leading processing at up to 3.2 Terabits per second. With the immense growth in mobile devices, video, and private and public clouds, the pace of networking innovation is increasing. Software Defined Networks (SDNs) and other innovations are rapidly evolving to meet this challenge, but require the introduction of new protocols. Traditional merchant switch silicon with FIXED architectures need to be re-engineered to support new protocols, resulting in switches that lag 3 to 4 years behind the requirements. XPA allows XPliant switch silicon to gain new features in place, without even removing the cables from the installed switch. An example of a new requirement is VXLAN – which became a requirement for SDN overlays. New switch silicon needed to be developed to support VXLAN – obsoleting existing switches and requiring the purchase new switches to implement the new feature. The latest feature required is GENEVE – which the XPliant team has already added to the CNX880XX. Part Number IO Throughput 1/10GE ports 25GE ports 40/50GE ports* 40GE ports** 100GE ports SERDES CNX88091 3.20 Tbps 128 128 64 32 32 128x25G CNX88072 1.72 Tbps 72 72 36 18 18 72x25G CNX88071 1.28 Tbps 128 n/a n/a 32 n/a 128x10G
https://barefootnetworks.com/ 2005年秋季，Clean State项目已经在斯坦福成立，作为项目主管的Nick Mckeown教授和他的学生Martin Casado，来自伯克利的Scott Shenker教授，来自Princeton的Larry Peterson教授和Jennifer Rexford等人办了一系列研讨会，探讨如何革新互联网。当时主讲人还包括了有着“互联网之父”称号的Vint Cerf，谈论到互联网创新并没有结束。 这个研讨会一直持续到了2007年。这一年，Nick Mckeown、Martin Casado和Scott Shenker创立了Nicira Networks公司，试图将Clean State的学术研究转化为工业实践。这个公司几乎标志着“软件定义网络(SDN)”这个产业的诞生，尽管这个词在2009年才被发明出来。 在这之后，OpenFlow协议诞生，这是软件定义网络的基础协议。Clean State项目和Nicira成为了OpenFlow的大本营，接连发布了NOX和Open vSwitch作为OpenFlow的重要组件。OpenFlow的成功也导致Nick Mckeown的另一个博士生Guido Appenzeller和Clean State项目中的访问学者Rob Sherwood创立了BigSwitch Networks公司，致力于发展OpenFlow技术，为这个行业打造了一系列开源工具，稳坐行业第二把交椅。 2012年，Nicira被VMware以12.6亿美金天价收购，堪称SDN行业的引爆点，SDN的初创企业和企业应用开始如雨后春笋兴起。 在Nick Mckeown的演讲中，SDN的第一步是在兼容现有硬件设备的前提下发展软件。Nicira和BigSwitch为此而诞生，而Nick Mckeown的四个博士生David Erickson、Nikhil Handigol、Brandon Heller和Peyman Kazemian则创立了面向企业用户的Forward Network，帮助企业建立更可靠的网络系统。 SDN的第二步则是发展为它专门优化的硬件设备。Nick Mckeown和Jennifer Rexford发起了对数据包进行处理的编程语言P4，这实际上回应了Nick发展SDN的初心，帮助网络用户摆脱被芯片硬件厂商各种协议的制约。然后，Nick和一起玩P4的小伙伴们成立了Barefoot Networks公司，致力于开发基于P4的网络芯片Tofino和软件开发套件Capilano，并帮助P4社区发展壮大。 这可以解释为什么Sequoia、Andreessen Horowitz、Lightspeed、Google、高盛、阿里和腾讯一起投资了它，业界将它视为下一个Nicira，而融资额是Nicira当年的4倍。当年Nicira的创始人Martin Casado刚从VMware辞职并加入Andreessen Horowitz不久，就参与了这宗投资，也算是对导师的信仰。从谷歌Fiber项目出来不久的Craig Barrett，也加盟了这家初创公司，成为了CEO。 不过话说回来，热门技术并不意味着优秀的商业价值，并且Barefoot要在一帮巨头的战争中生存，也是压力山大。 斯坦福Clean State项目在2012年终止运行。作为SDN的起源，这个项目算是圆满完成任务，将SDN的血脉传承给了其他的组织。现在，你依然可以这个项目的网页上看到它最初的使命：“重新发明互联网”。 Barefoot Tofino is the world’s first end-user programmable Ethernet switch. It is built using a Protocol Independent Switch Architecture (PISA) and is P4-programmable. Tofino gives network designers the power of the Protocol-Independent Switch Architecture (PISA). The PISA architecture was developed to provide powerful programmability. Tofino is fully programmable because the forwarding logic resides in the P4 program that the network operator or switch manufacturer loads on the chip; it's not baked into the silicon. Tofino is protocol independent because the chip has no awareness of the network protocols it supports. Instead, the P4 program provides the logic for handling all supported protocols. When support for a new protocol is required, the network operator or switch manufacturer simply adds new logic to the P4 program. 《Barefoot发布基于Tofino芯片的Wedge 100B交换机系列》 Barefoot Networks还将展示使用了Tofino芯片的Wedge 100B系列交换机，包括Wedge100BF-32X，3.2Tb / s 1RU 32x100GE交换机和Wedge100BF-65X，6.5Tb / s 2RU 65x100GE交换机。该系列交换机不仅让用户具备高性能，而且还是完全可编程的以太网交换机。Wedge 100B交换机支持FBOSS，SONiC和其他几种交换机操作系统，可以通过OCP的交换机抽象接口（SAI）API、switchAPI（可扩展的，开放的API）或用户设计的API加以控制。在Tofino上运行的默认“switch.p4”程序将Wedge 100B交换机转换为机架顶交换机，具有数据中心所需的所有标准功能。用户可以根据自己的选择增加或删除功能、增加新协议、更改流表大小，提供更多的可是话和中间件功能，如4层负载均衡。Wedge 100B平台还引入了一些增强功能，包括优化的供电单元，更低成本的PCB设计，改进的可制造性设计，更强大的CPU模块等。目前该交换机运行的是最新版本的OpenBMC。
知乎：https://www.zhihu.com/question/27336289/answer/92617122?from=profile_answer_card
目前，业界比较流行的有OpenDaylight(ODL)、ONOS、OpenContrail、Ryu、Floodlight等SDN控制器; 目前基于ODL技术部署的SDN控制器有 61%市场客户，适合大部分企业和OTT运营商; 基于ONOS技术的SDN控制器有23%市场客户。 目前来看，ODL影响还是比ONOS更为广泛更加实用，ODL更多的是关注南向的代码和协议和现有设备的兼容性更好一些， 基于ODL的开发的编排器方案相对较多，笔者认为不论选择哪种开源技术， 需要考虑控制器对开放接口支持程度、调用方便、是否易于扩展和功能完善能力，包括： 需要考虑开源版本、升级支持、HA和集群的负载分担能力，大业务的并发处理能力、软件定制化或开发能力、避免Bug和坑等等。尽量选择有专业开发能力和SDN集成解决方案的实力SDN软件服务商，目前国内专注于SDN领域和并具备开发能力的SDN公司还不算太多，大地云网公司专注于SDN/NFV/云网融合等领域，是一家不错的选择。 WIKI：https://en.wikipedia.org/wiki/List_of_SDN_controller_software Open and community driven initiatives: Open Daylight (controller baseline project upon which many other controllers are built) ONOS Project Calico The Fast Data Project Project Floodlight Beacon NOX/POX Open vSwitch vneio/sdnc (SDN Controller from vne.io) Ryu Controller (supported by NTT Labs) Cherry Faucet (Python based on Ryu for production networks) OpenContrail
https://www.sdnlab.com/14589.html 目前交换机芯片市场被Broadcom（博通）高度垄断，BRCM占据90%的市场份额。除了大户Google/Facebook等互联网公司，Google实际上是业内第二大的交换机厂家，之前只采用自研芯片的Cisco在nexus系列交换机中也开始采用BRCM商用芯片，有一篇文章讲Cisco通过采用商业芯片将N9K的研发周期缩短至不到一年。芯片既烧钱又费时，所以目前国内土豪紫光接连出手收购半导体公司。可想而知Broadcom交换机芯片的margin非常高，这也导致Broadcom公司对新技术的反应速度就慢很多，店大欺客是必须的！比如目前大家都在诟病OpenFlow应用中Broadcom公司的交换芯片流表大小有限，再比如对OpenFlow的支持，直到OpenFlow已经到了1.3版本Broadcom公司才推出了改进后的OF-DPA 2.0版本。 既然有痛点，就有新公司跳出来挑战霸主（分一杯羹），美国有xPliant（被Cavium收购），barefoot等，中国有盛科/联发科/海思等都想借SDN的风口飞一把。如果交换机的操作系统绑定到某家公司的交换芯片上，比如某些互联网公司采用Broadcom公司自家的fastpath/icos软件，初期看上去很好很方便，如果有一天想利用Cavium（xPliant）的大流表，Barefoot的协议无关时就变得很傻很天真了，因为系统不具有任何可移植性。 之前大部分商业交换机就是一个黑盒子，买Cisco就带NX-OS/iOS，买H3C就带Commvare。白牌交换机的出现使得交换机可以选择操作系统成为可能，如同买PC可以安装Windows，也可以安装Linux一样。目前提供第三方独立交换机操作系统的主要有Pica8/Big Switch/Cumulus等公司，HP公司推出的OpenSwitch目前还处于发展初期暂时不考虑。Big Switch公司曾经以floodlight控制器惊艳一枪，但是新技术的发展总不是一帆风顺，在被Cisco从OpenDaylight组织中排挤出局后公司几经沉浮，创业团队大换血。目前BSN公司战略也下沉到交换机提供纯Openflow交换机OS，但不具备任何传统2/3层协议功能。 Cumulus创始团队也很豪华，来自Cisco的老兵JR想利用低成本的白牌交换机挑战Cisco，复制Arista的成功之路。Cumulus将传统网络协议Linux化，让大型数据中心的IT人员可以管理交换机，也就是说让CCIE通通下岗。目前这种做法在北美的大型数据中心以及一些实验环境有一定市场。但是据说国内BAT接洽后相互都没能对上眼，网络规模和企业文化都不匹配，所以Cumulus的主要精力也放在北美，等待被大鳄收购。 Pica8走中间路线，同时支持传统网络协议和OpenFlow技术，同时基于专利CrossFlow技术实现两种协议在单台设备间的互通。我们基于自家的交换机，利用CrossFLow特性实现了办公室网络流量的QoS管理，在传统网络中用openflow流表来区分业务赋予不同优先级和通路。 另外一个值得关注的交换机OS是HP刚刚推出的开源交换机操作系统OpenSwitch，注意不是OpenvSwitch，少个v，目前支持自家以及智邦的几款硬件平台。OpenSwitch最核心的系统状态数据库就是OVSDB。系统目前还处于初级阶段，所以协议支持种类有限，三层协议基于开源的Quagga，另外OpenSwitch目前还不支持openflow。
原文：http://blog.csdn.net/jmilk/article/details/51824935 全虚拟化 不需要对GuestOS操作系统软件的源代码做任何的修改，就可以运行在这样的VMM中 在全虚拟化的虚拟平台中，GuestOS并不知道自己是一台虚拟机，它会认为自己就是运行在计算机物理硬件设备上的HostOS。因为全虚拟化的VMM会将一个OS所能够操作的CPU、内存、外设等物理设备逻辑抽象成为虚拟CPU、虚拟内存、虚拟外设等虚拟设备后，再交由GuestOS来操作使用。这样的GuestOS会将底层硬件平台视为自己所有的，但是实际上，这些都是VMM为GuestOS制造了这种假象。 全虚拟化又分为：软件辅助的全虚拟化 & 硬件辅助的全虚拟化。 软件辅助的全虚拟化 软件辅助全虚拟化架构图： 在Intel等CPU厂商还没有发布x86 CPU虚拟化技术之前，完全虚拟化都是通过软件辅助的方式来实现的。而软件辅助的全虚拟化主要是应用了两种机制： 1. 特权解除(优先级压缩)：从上述的软件辅助全虚拟化架构图中可以看出，VMM、GuestOS、GuestApplications都是运行在Ring 1-3用户态中的应用程序代码。当在GuestOS中执行系统内核的特权指令时，一般都会触发异常。这是因为用户态代码不能直接运行在核心态中，而且系统内核的特权指令大多都只能运行在Ring 0核心态中。在触发了异常之后，这些异常就会被VMM捕获，再由VMM将这些特权指令进行虚拟化成为只针对虚拟CPU起作用的虚拟特权指令。其本质就是使用若干能运行在用户态中的非特权指令来模拟出只针对GuestOS有效的虚拟特权指令，从而将特权指令的特权解除掉。 缺点：但是特权解除的问题在于当初设计标准x86架构CPU时，并没有考虑到要支持虚拟化技术，所以会存在一部分特权指令运行在Ring 1用户态上，而这些运行在Ring 1上的特权指令并不会触发异常然后再被VMM捕获。从而导致在GuestOS中执行的特权指令直接对HostOS造成了影响(GuestOS和HostOS没能做到完全隔离)。 针对这个问题，再引入了陷入模拟的机制。 陷入模拟(二进制翻译)：就是VMM会对GuestOS中的二进制代码(运行在CPU中的代码)进行扫描，一旦发现GuestOS执行的二进制代码中包含有运行在用户态上的特权指令二进制代码时，就会将这些二进制代码翻译成虚拟特权指令二进制代码或者是翻译成运行在核心态中的特权指令二进制代码从而强制的触发异常。这样就能够很好的解决了运行在Ring 1用户态上的特权指令没有被VMM捕获的问题，更好的实现了GuestOS和HostOS的隔离。 简而言之，软件辅助虚拟化能够成功的将所有在GuestOS中执行的系统内核特权指令进行捕获、翻译，使之成为只能对GuestOS生效的虚拟特权指令。但是退一步来说，之所以需要这么做的前提是因为CPU并不能准确的去判断一个特权指令到底是由GuestOS发出的还是由HostOS发出的，这样也就无法针对一个正确的OS去将这一个特权指令执行。 直到后来CPU厂商们发布了能够判断特权指令归属的标准x86 CPU之后，迎来了硬件辅助全虚拟化。 硬件辅助的全虚拟化 硬件辅助全虚拟化主要使用了支持虚拟化功能的CPU进行支撑，CPU可以明确的分辨出来自GuestOS的特权指令，并针对GuestOS进行特权操作，而不会影响到HostOS。 从更深入的层次来说，虚拟化CPU形成了新的CPU执行状态 —— * Non-Root Mode& Root Mode* 。从上图中可以看见，GuestOS运行在Non-Root Mode 的Ring 0核心态中，这表明GuestOS能够直接执行特却指令而不再需要 特权解除 和 陷入模拟 机制。并且在硬件层上面紧接的就是虚拟化层的VMM，而不需要HostOS。这是因为在硬件辅助全虚拟化的VMM会以一种更具协作性的方式来实现虚拟化 —— 将虚拟化模块加载到HostOS的内核中，例如：KVM，KVM通过在HostOS内核中加载KVM Kernel Module来将HostOS转换成为一个VMM。所以此时VMM可以看作是HostOS，反之亦然。这种虚拟化方式创建的GuestOS知道自己是正在虚拟化模式中运行的GuestOS，KVM就是这样的一种虚拟化实现解决方案。 半虚拟化 需要对GuestOS的内核代码做一定的修改，才能够将GuestOS运行在半虚拟化的VMM中。 半虚拟化通过在GuestOS的源代码级别上修改特权指令来回避上述的虚拟化漏洞。 修改内核后的GuestOS也知道自己就是一台虚拟机。所以能够很好的对核心态指令和敏感指令进行识别和处理，但缺点在于GuestOS的镜像文件并不通用。 具体的x86架构CPU解析，请参考虚拟化的发展历程和实现方式
目前分为两种，寄居架构（Hosted Architecture）和裸金属架构 (“Bare Metal” Architecture)，如图所示。 寄居架构就是在操作系统之上安装和运行虚拟化程序，依赖于主机操作系统对设备的支持和物理资源的管理; 裸金属架构就是直接在硬件上面安装虚拟化软件，再在其上安装操作系统和应用，依赖虚拟层内核和服务器控制台进行管理。 寄居架构
信息来源： http://www.pica8.com/products/hardware-compatibility-list https://cumulusnetworks.com/products/hardware-compatibility-list/ https://opennetlinux.org/hcl https://github.com/Azure/SONiC/wiki/Supported-Devices-and-Platforms DELL Z9100-ON ：32 x 100G，Tomahawk， intel X86 S4048-ON：48*10G/6*40G，Trident2， intel X86 S6000-ON：32 x 40G，Trident2， intel X86 S6010-ON：32 x 40G，Trident2， intel X86 S4810-ON： 48x10G + 4x40G，BCM56845 (Trident)，FreeScale P2020 DELTA(tw，台达） AG9032v1：32 x 100G，Tomahawk， intel X86 AG-7448CU：48*10G-T/4*40G，Trident，powerPC AG7648：48*10G-T/6*40G，Trident2， intel X86 edge-core/Accton AS7512-32X：32 x 100G，Cavium XP80， intel X86 AS7712-32X：32 x 100G，Tomahawk， intel X86 AS6701-32X：32 x 40G，Trident2，powerPC AS6712-32X：32 x 40G，Trident2， intel X86 AS6812-32X：32 x 40G，Trident2+， intel X86 AS5812-54T：48*10G/6*40G，Trident2+， intel X86 AS5812-54X：48*10G/6*40G，Trident2+， intel X86 AS5712-54X：48*10G/6*40G，Trident2， intel X86 AS5600-52X：48*10G/4*40G，Trident+， intel X86 OMP-800：256 x 100G，Tomahawk， intel X86 facebook backpack：128 x 100G，Tomahawk， intel X86 Wedge-100：32 x 100G，Tomahawk， intel X86 HP Altoline 6960：32 x 100G，Tomahawk， intel X86 Altoline 6940：32 x 40G，Trident2， intel X86 Altoline 6921：48*10G-T/6*40G，Trident2+， intel X86 Altoline 6920：48*10G-T/6*40G，Trident2， intel X86 Ingrasys（鸿佰科技，鸿海旗下） Ingrasys S9100-32X Broadcom Tomahawk 32x100G SONiC-ONIE-BroadcomIngrasys S8900-54XC Broadcom Tomahawk 48x25G+6x100G SONiC-ONIE-BroadcomIngrasys S8900-64XC Broadcom Tomahawk 48x25G+16x100G SONiC-ONIE-BroadcomIngrasys S8810-32Q Broadcom Trident2 32x40G SONiC-ONIE-Broadcom Interface Masters Technologies Niagara 2948X12XLm 48x10G + 12x40G Intel/AMD x86 BCM56850 (Trident2) Niagara 2960X6XLm 60x10G + 6x40G Intel/AMD x86 BCM56850 (Trident2) Niagara 2972Xm 72x10G Intel/AMD x86 BCM56850 (Trident2) Niagara 2932XL 32x40G Intel/AMD x86 BCM56850 (Trident2) Niagara 2948X6XL 48x10G + 6x40G Intel/AMD x86 BCM56850 (Trident2) inventec（tw，英业达） D7032Q28：32 x 100G，Tomahawk， intel X86 D70545 Broadcom Tomahawk 48x25G-6x100G Marvell Marvell RD-BC3-4825G6CG-A4 Marvell Prestera 98CX84xx 6x100G+48x25G Marvell RD-ARM-48XG6CG-A4 Marvell Prestera 98EX54xx 6x100G+48x10G Mellanox SN2100：16x 100G，Mellanox spectrum， intel X86 SN2700：32x 100G，Mellanox spectrum， intel X86 SN2740：32x 100G，Mellanox spectrum， intel X86 SN2700B：32x 40G，Mellanox spectrum， intel X86 SN2410： 48x25G + 8x100G Intel Ivybridge 1047UE Mellanox Spectrum Netberg Aurora 720 32x100G Intel Rangeley C2558 BCM56960 (Tomahawk) Aurora 620 48x10/25G + 6x40/100G Intel Rangeley C2558 BCM56960 (Tomahawk) PENGUIN Arctica 4806XP：48*10G-T/6*40G，Trident2+， intel X86 Arctica 3200C：32 x 100G，Tomahawk， intel X86 Arctica 3200XL：32 x 40G，Trident2，powerPC Arctica 3200XLP：32 x 40G，Trident2， intel X86 pica8 P-5401：32 x 40G，Trident2，powerPC P-5101：40*10G/8*40G，Trident2，powerPC P-3922: 48*10G/4*40G，Trident+，powerPC QCT （Quanta cloud tech） T3048-LY2：48*10G/4*40G，Trident+，powerPC QuantaMesh BMS T7032-IX1：32 x 100G，Tomahawk， intel X86 Device Ports CPU Forwarding ONL Ver Tested In Lab OF-DPA OpenNSL SAI QuantaMesh T3048-LY2 48x10G + 4x40G FreeScale P2020 BCM56846 (Trident+) 2.0.0 08b68ca Yes No No NoQuantaMesh T3048-LY8 48x10G + 6x40G Intel Rangeley C2758 x86 BCM56854 (Trident2) 2.0.0 0b3dd1b Yes No No NoQuantaMesh T3048-LY7 48x10G + 4x40G Intel Rangeley C2758 x86 BCM56854 (Trident2) 2.0.0 Yes No No NoQuantaMesh T5032-LY6 32x40G Intel Rangeley C2758 x86 BCM56850 (Trident2) 2.0.0 0b3dd1b Yes No No NoQuantaMesh T3048-LY9 48x10GT + 6x40G Intel Rangeley C2758 x86 BCM56850 (Trident2) 2.0.0 0b3dd1b Yes No No NoQuantaMesh T7032-IX1 32x100G Intel Rangeley C2558 x86 BCM56960 (Tomahawk) 2.0.0 fbc38a5 Yes No No NoQuantaMesh T7032-IX1B 32x100G Intel Rangeley C2558 x86 BCM56960 (Tomahawk) 2.0.0 fbc38a5 Yes No No NoQuantaMesh T4048-IX2 48x10G/25G + 8x10G/25G/40G/50G/100G Intel Rangeley C2558 x86 BCM56962 (Tomahawk) 2.0.0 fbc38a5 Yes No No No supermicro SSE-C3632S：32 x 100G，Tomahawk， intel X86 SSE-X3648S：48*10G-T/6*40G，Trident2， intel X86
WIKI NOS：https://en.wikipedia.org/wiki/Network_operating_system Examples: JUNOS, used in routers and switches from Juniper Networks Cisco Internetwork Operating System (IOS) IPOS, used in routers from Ericsson FortiOS, used in Fortigates from Fortinet TiMOS, used in routers from Alcatel-Lucent Versatile Routing Platform (VRP), used in routers from Huawei RouterOS, software which turns a PC or MikroTik hardware into a dedicated router ZyNOS, used in network devices made by ZyXEL. Extensible Operating System used in switches from Arista ExtremeXOS (EXOS), used in network devices made by Extreme Networks Embedded Linux, in distributions like Openwrt and DD-WRT which run on low-cost platforms such as the Linksys WRT54G Open source network operating system examples: Cumulus Linux distribution, which uses the full TCP/IP stack of Linux. Dell Networking Operating System (DNOS) is the new name for the operating system running on switches from Dell Networking; it will run atop NetBSD Open Network Operating System (ONOS) PicOS, Linux-based OpenFlow-supporting switching operating system from made by Pica8 VyOS, an open source fork of the Vyatta routing package OpenSwitch Linux Network Operating System from Hewlett-Packard.[3] -------------------------------------------------------------------------------------------------------------------------- 1、picOS (pica8) //trident, cavium, 支持白盒交换机列表：http://www.pica8.com/products/hardware-compatibility-list 特点： A Layer-2 protocol stack featuring MLAG Full Layer-3 protocol support including OSPF, BGP and multicast Support for OpenFlow, OVSDB, and key SDN protocols Integration with market-leading SDN controllers including HP VAN, ONOS, OpenDaylight, and Ryu Simple device provisioning and management via ZTP, CLI, DevOps automation tools, and a standard Linux shell 2、SnapRoute //?? Founded by engineers who created and reliably operated some of the largest data center networks on the planet by adopting open networking principles, SnapRoute is dedicated to bringing simplicity, reliability, and white-box economics to data center networks everywhere. SnapRoute’s FlexSwitch software runs on industry standard white-box switches, providing all management and networking functionality through an innovative architecture that simplifies the networking stack and dramatically reduces the code bloat typical of incumbent products. SnapRoute makes it easy to automate network provisioning while giving unprecedented visibility into how the network is running. SnapRoute is backed by Norwest Venture Partners, Lightspeed Venture Partners, AT&T, and Microsoft. 3、FBOSS(facebook) //barefoot github：https://github.com/facebook/fboss FBOSS is Facebook's software stack for controlling and managing network switches. 4、SONiC(azure) //trident, barefoot, caviun, centec github: https://github.com/Azure/SONiC SONiC is an open source project for network routers and switches. Switch Vendor Switch SKU ASIC Vendor Swich ASIC Port Configuration SONiC Image Arista 7050QX-32 Broadcom Trident2 32x40G SONiC-Aboot-Broadcom2 Arista 7050QX-32S Broadcom Trident2 32x40G SONiC-Aboot-Broadcom Arista 7060CX-32S Broadcom Tomahawk 32x100G SONiC-Aboot-Broadcom Barefoot Wedge 100BF-65X Barefoot Tofino-T10-064Q 65x100G Barefoot Wedge 100BF-32X Barefoot Tofino-T10-032D 32x100G Barefoot SONiC-P4 Barefoot P4 Emulated Configurable SONiC-P4 Centec E582-48x6q Centec Goldengate 6x40G + 48x10G SONiC-ONIE-Centec Dell S6000-ON3 Broadcom Trident2 32x40G SONiC-ONIE-Broadcom Dell S6100-ON3 Broadcom Tomahawk 64x40G 1 SONiC-ONIE-Broadcom Dell Z9100-ON3 Broadcom Tomahawk 32x100G SONiC-ONIE-Broadcom Delta AG9032V1 Broadcom Tomahawk 32x100G SONiC-ONIE-Broadcom Edgecore AS5712-54X Broadcom Trident2 72x10G SONiC-ONIE-Broadcom Edgecore AS7512-32X Cavium XPliant CNX880** 32x100G SONiC-ONIE-Cavium Edgecore AS7712-32X Broadcom Tomahawk 32x100G SONiC-ONIE-Broadcom Embedway ES6428A-X48Q2H4 Centec Goldengate 4x100G + 2x40G + 48x10G SONiC-ONIE-Centec Facebook Wedge 100-32X Broadcom Tomahawk 32x100G SONiC-ONIE-Broadcom Ingrasys S9100-32X Broadcom Tomahawk 32x100G SONiC-ONIE-Broadcom Ingrasys S8900-54XC Broadcom Tomahawk 48x25G+6x100G SONiC-ONIE-Broadcom Ingrasys S8900-64XC Broadcom Tomahawk 48x25G+16x100G SONiC-ONIE-Broadcom Ingrasys S8810-32Q Broadcom Trident2 32x40G SONiC-ONIE-Broadcom Inventec D7032-32X5 Broadcom Tomahawk 32x100G SONiC-ONIE-Broadcom Inventec D70545 Broadcom Tomahawk 48x25G-6x100G SONiC-ONIE-Broadcom Marvell RD-BC3-4825G6CG-A4 Marvell Prestera 98CX84xx 6x100G+48x25G SONiC-ONIE-Marvell Marvell RD-ARM-48XG6CG-A4 Marvell Prestera 98EX54xx 6x100G+48x10G SONiC-ONIE-Marvell Mellanox SN2700 Mellanox Spectrum 32x100G SONiC-ONIE-Mellanox Mellanox SN2740 Mellanox Spectrum 32x100G SONiC-ONIE-Mellanox Mellanox SN2410 Mellanox Spectrum 40x25G+8x100G SONiC-ONIE-Mellanox Mellanox SN2100 Mellanox Spectrum 16x100G SONiC-ONIE-Mellanox 5、Switch Light（bigswitch) // Switch Light™ is a Linux-based, thin switching software solution, providing consistent data plane programming abstractions across merchant silicon-based physical switches (white-box or brite-box) and hypervisor vSwitches. Switch Light is a key enabling technology for Big Switch Networks’ centralized SDN applications, and comes in two flavors: Switch Light OS: a complete SDN operating system based on Open Network Linux (ONL), an open source effort within the Open Compute Project. Switch Light VX: a user space software agent for KVM-based virtual switches that adds advanced functionality and improved performance on top of the Open vSwitch kernel. 6、Cumulus linux //trident, Mellanox Spectrum, The world’s most flexible open network operating system for bare metal switches。 支持单板列表：https://cumulusnetworks.com/products/hardware-compatibility-list 7，Pluribus //todo Netvisor OS fully supports OCP/ONIE switches, has best-in-class layer 2 and layer 3 networking, distributed fabric intelligence and virtualizes the switch hardware 8、ONOS ONOS is a new SDN network operating system designed for high availability, performance, scale-out. github: https://github.com/opennetworkinglab/onos >> ONL（open network linux） 源代码：https://github.com/OpenComputeProject/OpenNetworkLinux Open Network Linux is a Linux distribution for "bare metal" switches, that is, network forwarding devices built from commodity components. ONL uses ONIE to install onto on-board flash memory. Open Network Linux is a part of the Open Compute Project and is a component in a growing collection of open source and commercial projects.
1、总体设计 （https://www.edge-core.com/productsList.php?cls=1&cls2=5&cls3=67） 基于 Facebook’s Wedge 100 design. 30个QSFP28光模块 使用broadcom Tomahawk 3.2 Tbps 芯片 COM-E CPU module，Intel Atom E3800 x86 processor 支持ONIE 支持BMC 支持NOS：SnapRoute FlexSwitch software ，Open Network Linux （OCP） 2、PortsSwitch Ports:32 QSFP28 fixed ports:100 GbE/40 GbE or 4 x 25 GbE/4 x 10 GbE/ 2 x 50 GbE per portTotal Switch Capacity: 32 x 100 GbEManagement Ports (on port side):1 x RJ-45 serial console port to BMC1 x RJ-45 100/1000BASE-T management port1 x USB Type A storage portFacebook-specific debug portManagement Ports (on power side):1 x RJ-45 100/1000BASE-T management portFacebook-specific ports Supported Optics and Cables40GBASE-CR4 DAC; 0.5 m to 3 m; passive and active40GBASE-CR4 to 4 x SFP+ 10GBASE-CR DAC; 0.5 to 3 m40GBASE-SR4: 100 m over OM3 MMF, 150 m OM4 MMF40GBASE-SR4 to 4 x 10GBASE-SR: 100 m OM3, 150 m OM440GBASE-LR4: 10 km over SMF100GBASE-CR4 DAC; 0.5 m to 3 m; passive and active100GBASE-CR4 to 4 x SFP28 25G DAC; 0.5 to 3 m100GBASE-SR4: 100 m over OM3 MMF, 150 m OM4 MMF100GBASE-LR4: 10 km over SMFCat 5/6 cables for console and management ports 3、Key ComponentsSwitch Silicon: Broadcom BCM56960 Tomahawk 3.2 TbpsCPU Module: COM-E CPU module based on Intel Atom Processor E3800 family8GB SO-DIMM DDR3 1600MHz ECC2 x SATA 2.0 4、PerformanceSwitching Capacity: 3.2 Tbps full duplexForwarding Rate: 4.7 BppsJumbo frames support up to 9216 BytesPacket Buffer Size: 16 MB integrated packet bufferSubject to NOS:MAC Addresses: 8K min./136K max.VLAN IDs: 4KIPv4: 8K min./72K max. host entries; 16K LPM entries withTCAM-only modeIPv6: 4K//36K max. host entries; IPv6/64=8K TCAM-only mode 5、LEDs100G QSFP28 Ports: 2 LEDs per port for speed, activitySystem LEDs: Power, HeartbeatFan LEDs: on each fan module indicating status 6、PhysicalDimensions (WxDxH): 44 x 50.7 x 4.4 cm (17.32 x 19.97 x 1.732 in)Weight: 8.8 kg (19.56 lb)Fans: 4+1 redundant, hot-swappableFront (port) to back (power) airflow direction 7、EnvironmentalOperating Temperature: 0°C to 45°C (32°F to 113°F)Storage Temperature: -40°C to 70°C (-40°F to 158°F)Operating Humidity: 10% to 90% non-condensingStorage Humidity: 10% to 90% non-condensing 8、PowerPSUs: 2 redundant, load-sharing, hot-swappable AC or -54 VDCInput Voltage: 120 to 240 VAC at 50-60 Hz. 40 to 72 VDC.PSU Efficiency: Up to 93% for AC PSUsPower Input Option: 12 VDCTypical Power Consumption: 436 W 9、SoftwareSwitch is loaded with OpenBMCSwitch is loaded with DiagnosticsCompatible with FBOSS Agent open-source software from OCPCompatible with the following NOS options:1）Open Network Linux, the open-source, OCP reference NOS2）FlexSwitch software from SnapRoute3）Compatible with Cumulus Linux 3.4 and later version
如上图所示，AT&T将白盒生态系统分为4层。硬件1层（Hardware 1 Layer）：底层是商用芯片，在3月份的ONS大会上，AT&T高管宣布已经进行的开源白盒试验，通过使用博通和Barefoot的商用芯片进行试验。 软件1层（software 1 layer）：芯片接口，该层提取了芯片的功能，开源软件初创公司SnapRoute是AT&T在白盒化试验中操作系统的提供商，其他开源软件包括DPDK和交换机抽象接口（SAI），以及可编程语言P4。 硬件2层（hardware 2 layer）：网络功能的设计主要由OCP项目制定的标准化设计，AT&T表示其在已经举行的白盒试验中使用了Delta Electronics和Edgecore Networks的硬件，这两家公司是OCP硬件标准的主要贡献者。 软件2层（software 2 layer）：网络操作系统和相关协议，AT&T表示该层位于最顶层是最重要的，它实现了控制和管理平面的功能，并且作为将网络硬件和软件结合在一起的一层，只有这一层的功能是给最终用户使用。 AT&T支出SnapRoute、IP Infusion和Metaswitch是开发控制和管理平面的公司。IP Infusion提供白盒操作系统，支持多个厂商的产品以及交换路由协议。 白盒的先行者 在今年1月份，IHS Markit发布的一份调查报告中显示，85%的运营商计划在运行虚拟网络功能（VNF）时部署物理的uCPE，AT&T和Verizon是在白盒化道路上的先行者。Verizon产品和创新副总裁Shawn Hakl在NFV世界大会上表示，用户需要白盒，ADVA公司目前正在提供Verizon在白盒uCPE上运行的NFV技术。 AT&T与Barefoot Networks、博通、Delta Electronics、Edgecore Networks、Intel以及提供操作系统的SnapRoute公司达成合作，共同提供了白盒交换机。 在3月份完结的测试中，AT&T使用了带有博通Qumran芯片的Delta Agema AGC7648A交换机和SnapRoute网络操作系统（NOS）。在第二个位置使用的是Barefoot提供的基于Tofino芯片的Edgecore的Wedge 100BF交换机，运行的是SnapRoute的开放NOS FlexSwitch操作系统。此外，在3月完成的试验中，Intel基于架构的处理器运行了SnapRoute的NOS，管理了Barefoot和博通的芯片以及各种接口。 在3月底结束的相关试验中，AT&T测试的白盒交换机向ECOMP平台提供遥测，以监测从华盛顿到旧金山的流量状况
https://segmentfault.com/a/1190000006917884
以下是Linux系统调用的一个列表，包含了大部分常用系统调用和由系统调用派生出的的函数。 进程控制 系统调用 描述 fork 创建一个新进程 clone 按指定条件创建子进程 execve 运行可执行文件 exit 中止进程 _exit 立即中止当前进程 getdtablesize 进程所能打开的最大文件数 getpgid 获取指定进程组标识号 setpgid 设置指定进程组标志号 getpgrp 获取当前进程组标识号 setpgrp 设置当前进程组标志号 getpid 获取进程标识号 getppid 获取父进程标识号 getpriority 获取调度优先级 setpriority 设置调度优先级 modify_ldt 读写进程的本地描述表 nanosleep 使进程睡眠指定的时间 nice 改变分时进程的优先级 pause 挂起进程，等待信号 personality 设置进程运行域 prctl 对进程进行特定操作 ptrace 进程跟踪 sched_get_priority_max 取得静态优先级的上限 sched_get_priority_min 取得静态优先级的下限 sched_getparam 取得进程的调度参数 sched_getscheduler 取得指定进程的调度策略 sched_rr_get_interval 取得按RR算法调度的实时进程的时间片长度 sched_setparam 设置进程的调度参数 sched_setscheduler 设置指定进程的调度策略和参数 sched_yield 进程主动让出处理器,并将自己等候调度队列队尾 vfork 创建一个子进程，以供执行新程序，常与execve等同时使用 wait 等待子进程终止 wait3 参见wait waitpid 等待指定子进程终止 wait4 参见waitpid capget 获取进程权限 capset 设置进程权限 getsid 获取会晤标识号 setsid 设置会晤标识号 文件系统控制 文件读写操作 系统调用 描述 fcntl 文件控制 open 打开文件 creat 创建新文件 close 关闭文件描述字 read 读文件 write 写文件 readv 从文件读入数据到缓冲数组中 writev 将缓冲数组里的数据写入文件 pread 对文件随机读 pwrite 对文件随机写 lseek 移动文件指针 _llseek 在64位地址空间里移动文件指针 dup 复制已打开的文件描述字 dup2 按指定条件复制文件描述字 flock 文件加/解锁 poll I/O多路转换 truncat e 截断文件 ftruncate 参见truncate vumask 设置文件权限掩码 fsync 把文件在内存中的部分写回磁盘 文件系统操作 系统调用 描述 access 确定文件的可存取性 chdir 改变当前工作目录 fchdir 参见chdir chmod 改变文件方式 fchmod 参见chmod chown 改变文件的属主或用户组 fchown 参见chown lchown 参见chown chroot 改变根目录 stat 取文件状态信息 lstat 参见stat fstat 参见stat statfs 取文件系统信息 fstatfs 参见statfs readdir 读取目录项 getdents 读取目录项 mkdir 创建目录 mknod 创建索引节点 rmdir 删除目录 rename 文件改名 link 创建链接 symlink 创建符号链接 unlink 删除链接 readlink 读符号链接的值 mount 安装文件系统 umount 卸下文件系统 ustat 取文件系统信息 utime 改变文件的访问修改时间 utimes 参见utime quotactl 控制磁盘配额 系统控制 系统调用 描述 ioctl I/O总控制函数 _sysctl 读/写系统参数 acct 启用或禁止进程记账 getrlimit 获取系统资源上限 setrlimit 设置系统资源上限 getrusage 获取系统资源使用情况 uselib 选择要使用的二进制函数库 ioperm 设置端口I/O权限 iopl 改变进程I/O权限级别 outb 低级端口操作 reboot 重新启动 swapon 打开交换文件和设备 swapoff 关闭交换文件和设备 bdflush 控制bdflush守护进程 sysfs 取核心支持的文件系统类型 sysinfo 取得系统信息 adjtimex 调整系统时钟 alarm 设置进程的闹钟 getitimer 获取计时器值 setitimer 设置计时器值 gettimeofday 取时间和时区 settimeofday 设置时间和时区 stime 设置系统日期和时间 time 取得系统时间 times 取进程运行时间 uname 获取当前UNIX系统的名称、版本和主机等信息 vhangup 挂起当前终端 nfsservctl 对NFS守护进程进行控制 vm86 进入模拟8086模式 create_module 创建可装载的模块项 delete_module 删除可装载的模块项 init_module 初始化模块 query_module 查询模块信息 *get_kernel_syms 取得核心符号,已被query_module代替 内存管理 系统调用 描述 brk 改变数据段空间的分配 sbrk 参见brk mlock 内存页面加锁 munlock 内存页面解锁 mlockall 调用进程所有内存页面加锁 munlockall 调用进程所有内存页面解锁 mmap 映射虚拟内存页 munmap 去除内存页映射 mremap 重新映射虚拟内存地址 msync 将映射内存中的数据写回磁盘 mprotect 设置内存映像保护 getpagesize 获取页面大小 sync 将内存缓冲区数据写回硬盘 cacheflush 将指定缓冲区中的内容写回磁盘 网络管理 系统调用 描述 getdomainname 取域名 setdomainname 设置域名 gethostid 获取主机标识号 sethostid 设置主机标识号 gethostname 获取本主机名称 sethostname 设置主机名称 socket控制 系统调用 描述 socketcall socket系统调用 socket 建立socket bind 绑定socket到端口 connect 连接远程主机 accept 响应socket连接请求 send 通过socket发送信息 sendto 发送UDP信息 sendmsg 参见send recv 通过socket接收信息 recvfrom 接收UDP信息 recvmsg 参见recv listen 监听socket端口 select 对多路同步I/O进行轮询 shutdown 关闭socket上的连接 getsockname 取得本地socket名字 getpeername 获取通信对方的socket名字 getsockopt 取端口设置 setsockopt 设置端口参数 sendfile 在文件或端口间传输数据 socketpair 创建一对已联接的无名socket 用户管理 系统调用 描述 getuid 获取用户标识号 setuid 设置用户标志号 getgid 获取组标识号 setgid 设置组标志号 getegid 获取有效组标识号 setegid 设置有效组标识号 geteuid 获取有效用户标识号 seteuid 设置有效用户标识号 setregid 分别设置真实和有效的的组标识号 setreuid 分别设置真实和有效的用户标识号 getresgid 分别获取真实的,有效的和保存过的组标识号 setresgid 分别设置真实的,有效的和保存过的组标识号 getresuid 分别获取真实的,有效的和保存过的用户标识号 setresuid 分别设置真实的,有效的和保存过的用户标识号 setfsgid 设置文件系统检查时使用的组标识号 setfsuid 设置文件系统检查时使用的用户标识号 getgroups 获取后补组标志清单 setgroups 设置后补组标志清单 进程间通信 系统调用 描述 ipc 进程间通信总控制调用 信号 系统调用 描述 sigaction 设置对指定信号的处理方法 sigprocmask 根据参数对信号集中的信号执行阻塞/解除阻塞等操作 sigpending 为指定的被阻塞信号设置队列 sigsuspend 挂起进程等待特定信号 signal 参见signal kill 向进程或进程组发信号 *sigblock 向被阻塞信号掩码中添加信号,已被sigprocmask代替 *siggetmask 取得现有阻塞信号掩码,已被sigprocmask代替 *sigsetmask 用给定信号掩码替换现有阻塞信号掩码,已被sigprocmask代替 *sigmask 将给定的信号转化为掩码,已被sigprocmask代替 *sigpause 作用同sigsuspend,已被sigsuspend代替 sigvec 为兼容BSD而设的信号处理函数,作用类似sigaction ssetmask ANSI C的信号处理函数,作用类似sigaction 消息 系统调用 描述 msgctl 消息控制操作 msgget 获取消息队列 msgsnd 发消息 msgrcv 取消息 管道 系统调用 描述 pipe 创建管道 信号量 系统调用 描述 semctl 信号量控制 semget 获取一组信号量 semop 信号量操作 共享内存 系统调用 描述 shmctl 控制共享内存 shmget 获取共享内存 shmat 连接共享内存 shmdt 拆卸共享内存
http://blog.csdn.net/gatieme/article/details/50779184 系统调用概述 计算机系统的各种硬件资源是有限的，在现代多任务操作系统上同时运行的多个进程都需要访问这些资源，为了更好的管理这些资源进程是不允许直接操作的，所有对这些资源的访问都必须有操作系统控制。也就是说操作系统是使用这些资源的唯一入口，而这个入口就是操作系统提供的系统调用（System Call）。在linux中系统调用是用户空间访问内核的唯一手段，除异常和陷入外，他们是内核唯一的合法入口。 一般情况下应用程序通过应用编程接口API，而不是直接通过系统调用来编程。在Unix世界，最流行的API是基于POSIX标准的。 操作系统一般是通过中断从用户态切换到内核态。中断就是一个硬件或软件请求，要求CPU暂停当前的工作，去处理更重要的事情。比如，在x86机器上可以通过int指令进行软件中断，而在磁盘完成读写操作后会向CPU发起硬件中断。 中断有两个重要的属性，中断号和中断处理程序。中断号用来标识不同的中断，不同的中断具有不同的中断处理程序。在操作系统内核中维护着一个中断向量表（Interrupt Vector Table），这个数组存储了所有中断处理程序的地址，而中断号就是相应中断在中断向量表中的偏移量。 一般地，系统调用都是通过软件中断实现的，x86系统上的软件中断由int $0x80指令产生，而128号异常处理程序就是系统调用处理程序system_call()，它与硬件体系有关，在entry.S中用汇编写。接下来就来看一下Linux下系统调用具体的实现过程。 为什么需要系统调用 linux内核中设置了一组用于实现系统功能的子程序，称为系统调用。系统调用和普通库函数调用非常相似，只是系统调用由操作系统核心提供，运行于内核态，而普通的函数调用由函数库或用户自己提供，运行于用户态。 一般的，进程是不能访问内核的。它不能访问内核所占内存空间也不能调用内核函数。CPU硬件决定了这些（这就是为什么它被称作“保护模式”（详细参见深入理解计算机系统-之-内存寻址（二）–存储保护机制（CPU实模式与保护模式）））。 为了和用户空间上运行的进程进行交互，内核提供了一组接口。透过该接口，应用程序可以访问硬件设备和其他操作系统资源。这组接口在应用程序和内核之间扮演了使者的角色，应用程序发送各种请求，而内核负责满足这些请求(或者让应用程序暂时搁置)。实际上提供这组接口主要是为了保证系统稳定可靠，避免应用程序肆意妄行，惹出大麻烦。 系统调用在用户空间进程和硬件设备之间添加了一个中间层。该层主要作用有三个： 它为用户空间提供了一种统一的硬件的抽象接口。比如当需要读些文件的时候，应用程序就可以不去管磁盘类型和介质，甚至不用去管文件所在的文件系统到底是哪种类型。 系统调用保证了系统的稳定和安全。作为硬件设备和应用程序之间的中间人，内核可以基于权限和其他一些规则对需要进行的访问进行裁决。举例来说，这样可以避免应用程序不正确地使用硬件设备，窃取其他进程的资源，或做出其他什么危害系统的事情。 每个进程都运行在虚拟系统中，而在用户空间和系统的其余部分提供这样一层公共接口，也是出于这种考虑。如果应用程序可以随意访问硬件而内核又对此一无所知的话，几乎就没法实现多任务和虚拟内存，当然也不可能实现良好的稳定性和安全性。在Linux中，系统调用是用户空间访问内核的惟一手段；除异常和中断外，它们是内核惟一的合法入口。 API/POSIX/C库的区别与联系 一般情况下，应用程序通过应用编程接口(API)而不是直接通过系统调用来编程。这点很重要，因为应用程序使用的这种编程接口实际上并不需要和内核提供的系统调用一一对应。 一个API定义了一组应用程序使用的编程接口。它们可以实现成一个系统调用，也可以通过调用多个系统调用来实现，而完全不使用任何系统调用也不存在问题。实际上，API可以在各种不同的操作系统上实现，给应用程序提供完全相同的接口，而它们本身在这些系统上的实现却可能迥异。 在Unix世界中，最流行的应用编程接口是基于POSIX标准的，其目标是提供一套大体上基于Unix的可移植操作系统标准。POSIX是说明API和系统调用之间关系的一个极好例子。在大多数Unix系统上，根据POSIX而定义的API函数和系统调用之间有着直接关系。 Linux的系统调用像大多数Unix系统一样，作为C库的一部分提供如下图所示。C库实现了 Unix系统的主要API，包括标准C库函数和系统调用。所有的C程序都可以使用C库，而由于C语言本身的特点，其他语言也可以很方便地把它们封装起来使用。 从程序员的角度看，系统调用无关紧要，他们只需要跟API打交道就可以了。相反，内核只跟系统调用打交道；库函数及应用程序是怎么使用系统调用不是内核所关心的。 关于Unix的界面设计有一句通用的格言“提供机制而不是策略”。换句话说，Unix的系统调用抽象出了用于完成某种确定目的的函数。至干这些函数怎么用完全不需要内核去关心。区别对待机制(mechanism)和策略(policy)是Unix设计中的一大亮点。大部分的编程问题都可以被切割成两个部分:“需要提供什么功能”(机制)和“怎样实现这些功能”(策略)。 区别 api是函数的定义，规定了这个函数的功能，跟内核无直接关系。而系统调用是通过中断向内核发请求，实现内核提供的某些服务。 联系 一个api可能会需要一个或多个系统调用来完成特定功能。通俗点说就是如果这个api需要跟内核打交道就需要系统调用，否则不需要。 程序员调用的是API（API函数），然后通过与系统调用共同完成函数的功能。 因此，API是一个提供给应用程序的接口，一组函数，是与程序员进行直接交互的。 系统调用则不与程序员进行交互的，它根据API函数，通过一个软中断机制向内核提交请求，以获取内核服务的接口。 并不是所有的API函数都一一对应一个系统调用，有时，一个API函数会需要几个系统调用来共同完成函数的功能，甚至还有一些API函数不需要调用相应的系统调用（因此它所完成的不是内核提供的服务） 系统调用的实现原理 基本机制 前文已经提到了Linux下的系统调用是通过0x80实现的，但是我们知道操作系统会有多个系统调用（Linux下有319个系统调用），而对于同一个中断号是如何处理多个不同的系统调用的？最简单的方式是对于不同的系统调用采用不同的中断号，但是中断号明显是一种稀缺资源，Linux显然不会这么做；还有一个问题就是系统调用是需要提供参数，并且具有返回值的，这些参数又是怎么传递的？也就是说，对于系统调用我们要搞清楚两点： 系统调用的函数名称转换。 系统调用的参数传递。 首先看第一个问题。实际上，Linux中每个系统调用都有相应的系统调用号作为唯一的标识，内核维护一张系统调用表，sys_call_table，表中的元素是系统调用函数的起始地址，而系统调用号就是系统调用在调用表的偏移量。在x86上，系统调用号是通过eax寄存器传递给内核的。比如fork（）的实现： 用户空间的程序无法直接执行内核代码。它们不能直接调用内核空间中的函数，因为内核驻留在受保护的地址空间上。如果进程可以直接在内核的地址空间上读写的话，系统安全就会失去控制。所以，应用程序应该以某种方式通知系统，告诉内核自己需要执行一个系统调用，希望系统切换到内核态，这样内核就可以代表应用程序来执行该系统调用了。 通知内核的机制是靠软件中断实现的。首先，用户程序为系统调用设置参数。其中一个参数是系统调用编号。参数设置完成后，程序执行“系统调用”指令。x86系统上的软中断由int产生。这个指令会导致一个异常：产生一个事件，这个事件会致使处理器切换到内核态并跳转到一个新的地址，并开始执行那里的异常处理程序。此时的异常处理程序实际上就是系统调用处理程序。它与硬件体系结构紧密相关。 新地址的指令会保存程序的状态，计算出应该调用哪个系统调用，调用内核中实现那个系统调用的函数，恢复用户程序状态，然后将控制权返还给用户程序。系统调用是设备驱动程序中定义的函数最终被调用的一种方式。 从系统分析的角度，linux的系统调用涉及4个方面的问题。 响应函数sys_xxx 响应函数名以“sys_”开头，后跟该系统调用的名字。 例如 系统调用fork()的响应函数是sys_fork()(见Kernel/fork.c), exit()的响应函数是sys_exit()(见kernel/fork.)。 系统调用表与系统调用号-=>数组与下标 文件include/asm/unisted.h为每个系统调用规定了唯一的编号。 进程的系统调用命令转换为INT 0x80中断的过程 宏定义_syscallN()见include/asm/unisted.h)用于系统调用的格式转换和参数的传递。N取0~5之间的整数。 参数个数为N的系统调用由_syscallN()负责格式转换和参数传递。系统调用号放入EAX寄存器，启动INT 0x80后，规定返回值送EAX寄存器。 系统调用功能模块的初始化 对系统调用的初始化也就是对INT 0x80的初始化。 系统启动时，汇编子程序setup_idt(见arch/i386/kernel/head.S)准备了1张256项的idt表，由start_kernel()(见init/main.c),trap_init()(见arch/i386/kernel/traps.c)调用的C语言宏定义set_system_gate(0x80,&system_call)(见include/asm/system.h)设置0x80号软中断的服务程序为 system_call(见arch/i386/kernel/entry.S), system.call就是所有系统调用的总入口。 内核如何为各种系统调用服务 当进程需要进行系统调用时，必须以C语言函数的形式写一句系统调用命令。该命令如果已在某个头文件中由相应的_syscallN()展开，则用户程序必须包含该文件。当进程执行到用户程序的系统调用命令时，实际上执行了由宏命令_syscallN()展开的函数。系统调用的参数 由各通用寄存器传递，然后执行INT 0x80，以内核态进入入口地址system_call。 ret_from_sys_call 以ret_from_sys_call入口的汇编程序段在linux进程管理中起到了十分重要的作用。 所有系统调用结束前以及大部分中断服务返回前，都会跳转至此处入口地址。 该段程序不仅仅为系统调用服务，它还处理中断嵌套、CPU调度、信号等事务。 内核如何为系统调用的参数传递参数 参数传递 除了系统调用号以外，大部分系统调用都还需要一些外部的参数输人。所以，在发生异常的时候，应该把这些参数从用户空间传给内核。最简单的办法就是像传递系统调用号一样把这些参数也存放在寄存器里。在x86系统上，ebx, ecx, edx, esi和edi按照顺序存放前五个参数。需要六个或六个以上参数的情况不多见，此时，应该用一个单独的寄存器存放指向所有这些参数在用户空间地址的指针。 给用户空间的返回值也通过寄存器传递。在x86系统上，它存放在eax寄存器中。接下来许多关于系统调用处理程序的描述都是针对x86版本的。但不用担心，所有体系结构的实现都很类似。 参数验证 系统调用必须仔细检查它们所有的参数是否合法有效。举例来说，与文件I/O相关的系统调用必须检查文件描述符是否有效。与进程相关的函数必须检查提供的PID是否有效。必须检查每个参数，保证它们不但合法有效，而且正确。 最重要的一种检查就是检查用户提供的指针是否有效。试想，如果一个进程可以给内核传递指针而又无须被检查，那么它就可以给出一个它根本就没有访问权限的指针，哄骗内核去为它拷贝本不允许它访问的数据，如原本属于其他进程的数据。在接收一个用户空间的指针之前，内核必须保证： 指针指向的内存区域属于用户空间。进程决不能哄骗内核去读内核空间的数据。 指针指向的内存区域在进程的地址空间里。进程决不能哄骗内核去读其他进程的数据。 如果是读，该内存应被标记为可读。如果是写，该内存应被标记为可写。进程决不能绕过内存访问限制。 内核提供了两个方法来完成必须的检查和内核空间与用户空间之间数据的来回拷贝。注意，内核无论何时都不能轻率地接受来自用户空间的指针!这两个方法中必须有一个被调用。为了向用户空间写入数据，内核提供了copy_to_user()，它需要三个参数。第一个参数是进程空间中的目的内存地址。第二个是内核空间内的源地址。最后一个参数是需要拷贝的数据长度(字节数)。 为了从用户空间读取数据，内核提供了copy_from_ user()，它和copy-to-User()相似。该函数把第二个参数指定的位置上的数据拷贝到第一个参数指定的位置上，拷贝的数据长度由第三个参数决定。 如果执行失败，这两个函数返回的都是没能完成拷贝的数据的字节数。如果成功，返回0。当出现上述错误时，系统调用返回标准-EFAULT。 注意copy_to_user()和copy_from_user()都有可能引起阻塞。当包含用户数据的页被换出到硬盘上而不是在物理内存上的时候，这种情况就会发生。此时，进程就会休眠，直到缺页处理程序将该页从硬盘重新换回物理内存。 系统调用的返回值 系统调用(在Linux中常称作syscalls)通常通过函数进行调用。它们通常都需要定义一个或几个参数(输入)而且可能产生一些副作用，例如写某个文件或向给定的指针拷贝数据等等。为防止和正常的返回值混淆，系统调用并不直接返回错误码，而是将错误码放入一个名为errno的全局变量中。通常用一个负的返回值来表明错误。返回一个0值通常表明成功。如果一个系统调用失败，你可以读出errno的值来确定问题所在。通过调用perror()库函数，可以把该变量翻译成用户可以理解的错误字符串。 errno不同数值所代表的错误消息定义在errno.h中，你也可以通过命令”man 3 errno”来察看它们。需要注意的是，errno的值只在函数发生错误时设置，如果函数不发生错误，errno的值就无定义，并不会被置为0。另外，在处理errno前最好先把它的值存入另一个变量，因为在错误处理过程中，即使像printf()这样的函数出错时也会改变errno的值。 当然，系统调用最终具有一种明确的操作。举例来说，如getpid()系统调用，根据定义它会返回当前进程的PID。内核中它的实现非常简单: asmlinkage long sys_ getpid(void) { return current-> tgid; } 上述的系统调用尽管非常简单，但我们还是可以从中发现两个特别之处。首先，注意函数声明中的asmlinkage限定词，这是一个小戏法，用于通知编译器仅从栈中提取该函数的参数。所有的系统调用都需要这个限定词。其次，注意系统调用get_pid()在内核中被定义成sys_ getpid。这是Linux中所有系统调用都应该遵守的命名规则。 访问系统调用 系统调用上下文 内核在执行系统调用的时候处于进程上下文。current指针指向当前任务，即引发系统调用的那个进程。 在进程上下文中，内核可以休眠并且可以被抢占。这两点都很重要。首先，能够休眠说明系统调用可以使用内核提供的绝大部分功能。休眠的能力会给内核编程带来极大便利。在进程上下文中能够被抢占，其实表明，像用户空间内的进程一样，当前的进程同样可以被其他进程抢占。因为新的进程可以使用相同的系统调用，所以必须小心，保证该系统调用是可重人的。当然，这也是在对称多处理中必须同样关心的问题。 当系统调用返回的时候，控制权仍然在system_call()中，它最终会负责切换到用户空间并让用户进程继续执行下去。 系统调用访问示例 操作系统使用系统调用表将系统调用编号翻译为特定的系统调用。系统调用表包含有实现每个系统调用的函数的地址。例如，read() 系统调用函数名为sys_read。read()系统调用编号是 3，所以sys_read() 位于系统调用表的第四个条目中（因为系统调用起始编号为0）。从地址 sys_call_table + (3 * word_size) 读取数据，得到sys_read()的地址。 找到正确的系统调用地址后，它将控制权转交给那个系统调用。我们来看定义sys_read()的位置，即fs/read_write.c文件。这个函数会找到关联到 fd 编号（传递给 read() 函数的）的文件结构体。那个结构体包含指向用来读取特定类型文件数据的函数的指针。进行一些检查后，它调用与文件相关的 read() 函数，来真正从文件中读取数据并返回。与文件相关的函数是在其他地方定义的 —— 比如套接字代码、文件系统代码，或者设备驱动程序代码。这是特定内核子系统最终与内核其他部分协作的一个方面。 读取函数结束后，从sys_read()返回，它将控制权切换给 ret_from_sys。它会去检查那些在切换回用户空间之前需要完成的任务。如果没有需要做的事情，那么就恢复用户进程的状态，并将控制权交还给用户程序。 从用户空间直接访问系统调用 通常，系统调用靠C库支持。用户程序通过包含标准头文件并和C库链接，就可以使用系统调用(或者调用库函数，再由库函数实际调用)。但如果你仅仅写出系统调用，glibc库恐怕并不提供支持。值得庆幸的是，Linux本身提供了一组宏，用于直接对系统调用进行访问。它会设置好寄存器并调用陷人指令。这些宏是_syscalln()，其中n的范围从0到6。代表需要传递给系统调用的参数个数，这是由于该宏必须了解到底有多少参数按照什么次序压入寄存器。举个例子，open()系统调用的定义是: long open(const char *filename, int flags, int mode) 而不靠库支持，直接调用此系统调用的宏的形式为: #define NR_ open 5 syscall3(long, open, const char*，filename, int, flags, int, mode) 这样，应用程序就可以直接使用open() 对于每个宏来说，都有2+ n个参数。 第一个参数对应着系统调用的返回值类型。 第二个参数是系统调用的名称。再以后是按照系统调用参数的顺序排列的每个参数的类型和名称。 _NR_ open在<asm/unistd.h>中定义，是系统调用号。该宏会被扩展成为内嵌汇编的C函数。由汇编语言执行前一节所讨论的步骤，将系统调用号和参数压入寄存器并触发软中断来陷入内核。调用open()系统调用直接把上面的宏放置在应用程序中就可以了。 让我们写一个宏来使用前面编写的foo()系统调用，然后再写出测试代码炫耀一下我们所做的努力。 #define NR foo 283 _sysca110(long, foo) int main() { long stack size; stack_ size=foo(); printf("The kernel stack size is 81d/n"，stack_ size); return; }
http://blog.jobbole.com/107057/ 1. 为什么要软中断 编写驱动的时候，一个中断产生之后，内核在中断处理函数中可能需要完成很多工作。但是中断处理函数的处理是关闭了中断的。也就是说在响应中断时，系统不能再次响应外部的其它中断。这样的后果会造成有可能丢失外部中断。于是，linux内核设计出了一种架构，中断函数需要处理的任务分为两部分，一部分在中断处理函数中执行，这时系统关闭中断。另外一部分在软件中断中执行，这个时候开启中断，系统可以响应外部中断。 关于软件中断的理论各种书籍都有介绍，不多叙述。而要真正体会软件中断的作用就必须从代码的角度来分析。我们做工作时候讲求的是professional，当一个人在某个领域一无所知的时候，我们称他为小白，偶，非苹果电脑。小白的脑子里充满了各种问题。慢慢的当这些疑惑解释完之后，小白就脱白了。此时，我们对这个领域的基本框架有了解，但这和professional还有一定的差距。再加以时日，逐渐融会贯通该领域才能达到专业的境界。 2. 什么时候触发处理软件中断 说了这么多废话，赶快步入正题。初识软中断，脑子里肯定有不少的疑问，首先就是软件中断在什么地方被触发处理？这个问题的答案就是：一个硬件中断处理完成之后。下面的函数在处理完硬件中断之后推出中断处理函数，在irq_exit中会触发软件中断的处理。 asmlinkage void __exception asm_do_IRQ(unsigned int irq, struct pt_regs *regs) { struct pt_regs *old_regs = set_irq_regs(regs);irq_enter(); /* * Some hardware gives randomly wrong interrupts. Rather * than crashing, do something sensible. */ if (irq >= NR_IRQS) handle_bad_irq(irq, &bad_irq_desc); else generic_handle_irq(irq); /* AT91 specific workaround */ irq_finish(irq); irq_exit(); set_irq_regs(old_regs); } 这里要注意，invoke_softirq必须满足两个条件才能被调用到，一个就是不是在硬件中断处理过程中或者在软件中断处理中，第二个就是必须有软件中断处于pending状态。第二个好理解，有软件中断产生才去处理，没有就不处理。第一个就不好理解了。 /* * Exit an interrupt context. Process softirqs if needed and possible: */ void irq_exit(void) { account_system_vtime(current); trace_hardirq_exit(); sub_preempt_count(IRQ_EXIT_OFFSET); if (!in_interrupt() && local_softirq_pending()) invoke_softirq();#ifdef CONFIG_NO_HZ /* Make sure that timer wheel updates are propagated */ rcu_irq_exit(); if (idle_cpu(smp_processor_id()) && !in_interrupt() && !need_resched()) tick_nohz_stop_sched_tick(0); #endif preempt_enable_no_resched(); } 在linux系统的进程数据结构里，有这么一个数据结构 #define preempt_count()(current_thread_info()->preempt_count)， 利用preempt_count可以表示是否处于中断处理或者软件中断处理过程中。 #define PREEMPT_MASK (__IRQ_MASK(PREEMPT_BITS) #define SOFTIRQ_MASK (__IRQ_MASK(SOFTIRQ_BITS) #define HARDIRQ_MASK (__IRQ_MASK(HARDIRQ_BITS)#define PREEMPT_OFFSET (1UL #define SOFTIRQ_OFFSET (1UL #define HARDIRQ_OFFSET (1UL sub_preempt_count(IRQ_EXIT_OFFSET); #define in_interrupt()(irq_count()) #define irq_count()(preempt_count() & (HARDIRQ_MASK | SOFTIRQ_MASK)) preempt_count的8～23位记录中断处理和软件中断处理过程的计数。如果有计数，表示系统在硬件中断或者软件中断处理过程中。系统这么设计是为了避免软件中断在中断嵌套中被调用，并且达到在单个CPU上软件中断不能被重入的目的。对于ARM架构的CPU不存在中断嵌套中调用软件中断的问题，因为ARM架构的CPU在处理硬件中断的过程中是关闭掉中断的。只有在进入了软中断处理过程中之后才会开启硬件中断，如果在软件中断处理过程中有硬件中断嵌套，也不会再次调用软中断，because硬件中断是软件中断处理过程中再次进入的，此时preempt_count已经记录了软件中断！对于其它架构的CPU，有可能在触发调用软件中断前，也就是还在处理硬件中断的时候，就已经开启了硬件中断，可能会发生中断嵌套，在中断嵌套中是不允许调用软件中断处理的。Why？我的理解是，在发生中断嵌套的时候，表明这个时候是系统突发繁忙的时候，内核第一要务就是赶紧把中断中的事情处理完成，退出中断嵌套。避免多次嵌套，哪里有时间处理软件中断，所以把软件中断推迟到了所有中断处理完成的时候才能触发软件中断。 3. 软件中断的处理过程 之前我已经说到，软中断的一个很大的目的就是避免中断处理中，处理的操作过多而丢失中断。同时中断还需要考虑到一件事情就是中断处理过程过长就会影响系统响应时间。如果一个中断处理一秒钟，那你一定能感受到串口卡住的现象。从另外一方面说呢，我们又必须考虑中断处理的操作一定的优先度，毕竟是硬件触发的事务，关系到网络、块设备的效率问题。Linux内核就中断方面就必须考虑平衡这三个方面的问题。而下面我要分析的__do_softirq函数就恰似在这三者之间打太极，游刃有余，面面俱到！ /* * We restart softirq processing MAX_SOFTIRQ_RESTART times, * and we fall back to softirqd after that. * * This number has been established via experimentation. * The two things to balance is latency against fairness - * we want to handle softirqs as soon as possible, but they * should not be able to lock up the box. */ #define MAX_SOFTIRQ_RESTART 10asmlinkage void __do_softirq(void) { struct softirq_action *h; __u32 pending; int max_restart = MAX_SOFTIRQ_RESTART; int cpu;pending = local_softirq_pending(); account_system_vtime(current);__local_bh_disable((unsigned long)__builtin_return_address(0)); trace_softirq_enter(); cpu = smp_processor_id(); restart: /* Reset the pending bitmask before enabling irqs */ set_softirq_pending(0); local_irq_enable(); h = softirq_vec; do { if (pending & 1) { int prev_count = preempt_count(); h->action(h); if (unlikely(prev_count != preempt_count())) { printk(KERN_ERR "huh, entered softirq %td %p" "with preempt_count %08x," " exited with %08x?n", h - softirq_vec, h->action, prev_count, preempt_count()); preempt_count() = prev_count; } rcu_bh_qsctr_inc(cpu); } h++; pending >>= 1; } while (pending); local_irq_disable(); pending = local_softirq_pending(); if (pending && --max_restart) goto restart; if (pending) wakeup_softirqd(); trace_softirq_exit(); account_system_vtime(current); _local_bh_enable(); } __do_softirq函数处理软件中断过程如下图流程分析 4. 首先调用local_softirq_pending函数取得目前有哪些位存在软件中断 5. 调用__local_bh_disable关闭软中断，其实就是设置正在处理软件中断标记，在同一个CPU上使得不能重入__do_softirq函数 6. 重新设置软中断标记为0，set_softirq_pending重新设置软中断标记为0，这样在之后重新开启中断之后硬件中断中又可以设置软件中断位。 7. 开启硬件中断 8. 之后在一个循环中，遍历pending标志的每一位，如果这一位设置就会调用软件中断的处理函数。在这个过程中硬件中断是开启的，随时可以打断软件中断。这样保证硬件中断不会丢失。 9. 之后关闭硬件中断，查看是否又有软件中断处于pending状态，如果是，并且在本次调用__do_softirq函数过程中没有累计重复进入软件中断处理的次数超过10次，就可以重新调用软件中断处理。如果超过了10次，就调用wakeup_softirqd();唤醒内核的一个进程来处理软件中断。设立10次的限制，也是为了避免影响系统响应时间。 4. 处理软中断内核线程 之前我说到不能让CPU长时间来处理中断事务，这样会影响系统的响应时间，严重影响用户和系统之间的交互式体验。所以在之前的__do_softirq中最多将循环执行10次，那么当执行了10次仍然有软中断在pending状态，这个时候应该怎么处理呢？系统将唤醒一个软件中断处理的内核进程，在内核进程中处理pending中的软件中断。这里要注意，之前我们分析的触发软件中断的位置其实是中断上下文中，而在软中断的内核线程中实际已经是进程的上下文。 这里说的软中断上下文指的就是系统为每个CPU建立的ksoftirqd进程。 看完这个函数，我不得不佩服这个函数设计的精巧！而我更多的从中体会到其中蕴藏的一种做人的道理。那就是做人要霸道一点，太谦和太恭维不行，但是又不能横行霸道，原则的问题要公平讲理，一定的时候顾及别人的利益，好处不能一个人独吞。这就跟下面ksoftirqd处理过程一样，该狠的时候禁止抢占，其它进程别想调度到哦，但是自己占用CPU时间过长的话，也自觉的问一问是不是该释放CPU给其它进程了。 下面我们就来分析一下这个处理过程怎么就体现了上面的这种说法呢？软中断的内核进程中主要有两个大循环，外层的循环处理有软件中断就处理，没有软件中断就休眠。内层的循环处理软件中断，并每循环一次都试探一次是否过长时间占据了CPU，需要调度释放CPU给其它进程。具体的操作在注释中做了解释。 static int ksoftirqd(void *__bind_cpu) { set_current_state(TASK_INTERRUPTIBLE);while (!kthread_should_stop()) { /*不管三七二十一首先禁止抢占，我掌握CPU，并全凭我自己掌握调度*/ preempt_disable(); if (!local_softirq_pending()) { preempt_enable_no_resched(); /*如果没有软中断在pending，那就让出CPU来吧*/ schedule(); /*我被唤醒了，首先掌握CPU，不让自己被抢占，自己决定自己的是否要调度*/ preempt_disable(); }__set_current_state(TASK_RUNNING);while (local_softirq_pending()) { /* Preempt disable stops cpu going offline. If already offline, we'll be on wrong CPU: don't process */ if (cpu_is_offline((long)__bind_cpu)) goto wait_to_die; /*处理软中断*/ do_softirq(); /*虽然我自己掌握是否要调度，虽然我可以一直不调度，但是我是 个正直的人，运行一段时间后我会看看是否需要调度，还其它进程运行*/ preempt_enable_no_resched(); cond_resched(); preempt_disable(); rcu_qsctr_inc((long)__bind_cpu); } preempt_enable(); set_current_state(TASK_INTERRUPTIBLE); } __set_current_state(TASK_RUNNING); return 0; wait_to_die: preempt_enable(); /* Wait for kthread_stop */ set_current_state(TASK_INTERRUPTIBLE); while (!kthread_should_stop()) { schedule(); set_current_state(TASK_INTERRUPTIBLE); } __set_current_state(TASK_RUNNING); return 0; }
http://edsionte.com/techblog/archives/3223 1.线程 通过操作系统原理课，我们知道进程是系统资源分配的基本单位，线程是程序独立运行的基本单位。线程有时候也被称作小型进程，首先，这是因为多个线程之间是可以共享资源的；其次，多个线程之间的切换所花费的代价远远比进程低。 在用户态下，使用最广泛的线程操作接口即为POSIX线程接口，即pthread。通过这组接口可以进行线程的创建以及多线程之间的并发控制等。 2.轻量级进程 如果内核要对线程进行调度，那么线程必须像进程那样在内核中对应一个数据结构。进程在内核中有相应的进程描述符，即task_struct结构。事实上，从Linux内核的角度而言，并不存在线程这个概念。内核对线程并没有设立特别的数据结构，而是与进程一样使用task_struct结构进行描述。也就是说线程在内核中也是以一个进程而存在的，只不过它比较特殊，它和同类的进程共享某些资源，比如进程地址空间，进程的信号，打开的文件等。我们将这类特殊的进程称之为轻量级进程（Light Weight Process）。 按照这种线程机制的理解，每个用户态的线程都和内核中的一个轻量级进程相对应。多个轻量级进程之间共享资源，从而体现了多线程之间资源共享的特性。同时这些轻量级进程跟普通进程一样由内核进行独立调度，从而实现了多个进程之间的并发执行。 3.POSIX线程库的实现 用户线程和内核中轻量级进程的关联通常实在符合POSIX线程标准的线程库中完成的。支持轻量级进程的线程库有三个：LinuxThreads、NGPT（Next-Generation POSIX Threads）和NPTL（Native POSIX Thread Library）。由于LinuxThreads并不能完全兼容POSIX标准以及NGPT的放弃，目前Linux中所采用的线程库即为NPTL。 4.线程组 POSIX标准规定在一个多线程的应用程序中，所有线程都必须具有相同的PID。从线程在内核中的实现可得知，每个线程其实都有自己的pid。为此，Linux引入了线程组的概念。在一个多线程的程序中，所有线程形成一个线程组。每一个线程通常是由主线程创建的，主线程即为调用pthread_create()的线程。因此该线程组中所有线程的pid即为主线程的pid。 对于线程组中的线程来说，其task_struct结构中的tpid字段保存该线程组中主线程的pid，而pid字段则保存每个轻量级进程的本身的pid。对于普通的进程而言，tgid和pid是相同的。事实上，getpid()系统调用中返回的是进程的tgid而不是pid。 5.内核线程 上面所描述的都是用户态下的线程，而在内核中还有一种特殊的线程，称之为内核线程（Kernel Thread）。由于在内核中进程和线程不做区分，因此也可以将其称为内核进程。毫无疑问，内核线程在内核中也是通过task_struct结构来表示的。 内核线程和普通进程一样也是内核调度的实体，只不过他们有以下不同： 1).内核线程永远都运行在内核态，而不同进程既可以运行在用户态也可以运行在内核态。从另一个角度讲，内核线程只能之用大于PAGE_OFFSET（即3GB）的地址空间，而普通进程则可以使用整个4GB的地址空间。 2).内核线程只能调用内核函数，而普通进程必须通过系统调用才能使用内核函数。 6. do_fork()的多角色扮演 进程、线程以及内核线程都有对应的创建函数，不过这三者所对应的创建函数最终在内核都是由do_fork()进行创建的，具体的调用关系图如下： 从图中可以看出，内核中创建进程的核心函数即为看do_fork()，该函数的原型如下： long do_fork(unsigned long clone_flags, unsigned long stack_start, struct pt_regs *regs, unsigned long stack_size, int __user *parent_tidptr, int __user *child_tidptr) 该函数的参数个数是固定的，每个参数的功能如下： clone_flags：代表进程各种特性的标志。低字节指定子进程结束时发送给父进程的信号代码，一般为SIGCHLD信号，剩余三个字节是若干个标志或运算的结果。 stack_start：子进程用户态堆栈的指针，该参数会被赋值给子进程的esp寄存器。 regs：指向通用寄存器值的指针，当进程从用户态切换到内核态时通用寄存器中的值会被保存到内核态堆栈中。 stack_size：未被使用，默认值为0。 parent_tidptr：该子进程的父进程用户态变量的地址，仅当CLONE_PARENT_SETTID被设置时有效。 child_tidptr：该子进程用户态变量的地址，仅当CLONE_CHILD_SETTID被设置时有效。 既然进程、线程和内核线程在内核中都是通过do_fork()完成创建的，那么do_fork()是如何体现其功能的多样性？其实，clone_flags参数在这里起到了关键作用，通过选取不同的标志，从而保证了do_fork()函数实现多角色——创建进程、线程和内核线程——功能的实现。clone_flags参数可取的标志很多，下面只介绍几个与本文相关的标志。 CLONE_VIM：子进程共享父进程内存描述符和所有的页表。 CLONE_FS：子进程共享父进程所在文件系统的根目录和当前工作目录。 CLONE_FILES：子进程共享父进程打开的文件。 CLONE_SIGHAND：子进程共享父进程的信号处理程序、阻塞信号和挂起的信号。使用该标志必须同时设置CLONE_VM标志。 如果创建子进程时设置了上述标志，那么子进程会共享这些标志所代表的父进程资源。 6.1 进程的创建 在用户态程序中，可以通过fork()、vfork()和clone()三个接口函数创建进程，这三个函数在库中分别对应同名的系统调用。系统调用函数通过128号软中断进入内核后，会调用相应的系统调用服务例程。这三个函数对应的服务历程分别是sys_fork()、sys_vfork()和sys_clone()。 int sys_fork(struct pt_regs *regs) { return do_fork(SIGCHLD, regs->sp, regs, 0, NULL, NULL); } int sys_vfork(struct pt_regs *regs) { return do_fork(CLONE_VFORK | CLONE_VM | SIGCHLD, regs->sp, regs, 0, NULL, NULL); } long sys_clone(unsigned long clone_flags, unsigned long newsp, void __user *parent_tid, void __user *child_tid, struct pt_regs *regs) { if (!newsp) newsp = regs->sp; return do_fork(clone_flags, newsp, regs, 0, parent_tid, child_tid); } 通过上述系统调用服务例程的源码可以发现，三个服务历程内部都调用了do_fork()，只不过差别在于第一个参数所传的值不同。这也正好导致由这三个进程创建函数所创建的进程有不同的特性。下面对每种进程作以简单说明。 fork()：由于do_fork()中clone_flags参数除了子进程结束时返回给父进程的SIGCHLD信号外并无其他特性标志，因此由fork()创建的进程不会共享父进程的任何资源。子进程会完全复制父进程的资源，也就是说父子进程相对独立。不过由于写时复制技术（Copy On Write，COW）的引入，子进程可以只读父进程的物理页，只有当两者之一去写某个物理页时，内核此时才会将这个页的内容拷贝到一个新的物理页，并把这个新的物理页分配给正在写的进程。 vfork()：do_fork()中的clone_flags使用了CLONE_VFORK和CLONE_VM两个标志。CLONE_VFORK标志使得子进程先于父进程执行，父进程会阻塞到子进程结束或执行新的程序。CLONE_VM标志使得子进程共享父进程的内存地址空间（父进程的页表项除外）。在COW技术引入之前，vfork()适用子进程形成后立马执行execv()的情形。因此，vfork()现如今已经没有特别的使用之处，因为写实复制技术完全可以取代它创建进程时所带来的高效性。 clone()：clone通常用于创建轻量级进程。通过传递不同的标志可以对父子进程之间数据的共享和复制作精确的控制，一般flags的取值为CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND。由上述标志可以看到，轻量级进程通常共享父进程的内存地址空间、父进程所在文件系统的根目录以及工作目录信息、父进程当前打开的文件以及父进程所拥有的信号处理函数。 6.2 线程的创建 每个线程在内核中对应一个轻量级进程，两者的关联是通过线程库完成的。因此通过pthread_create()创建的线程最终在内核中是通过clone()完成创建的，而clone()最终调用do_fork()。 6.3 内核线程的创建 一个新内核线程的创建是通过在现有的内核线程中使用kernel_thread()而创建的，其本质也是向do_fork()提供特定的flags标志而创建的。 int kernel_thread(int (*fn)(void *), void *arg, unsigned long flags) { /*some register operations*/ return do_fork(flags | CLONE_VM | CLONE_UNTRACED, 0, &regs, 0, NULL, NULL); } 从上面的组合的flag可以看出，新的内核线程至少会共享父内核线程的内存地址空间。这样做其实是为了避免赋值调用线程的页表，因为内核线程无论如何都不会访问用户地址空间。CLONE_UNTRACED标志保证内核线程不会被任何进程所跟踪，
1、gedit：cannot open display derek@vbox:/home$ sudo geditInvalid MIT-MAGIC-COOKIE-1 keyUnable to init server: Could not connect: Connection refused (gedit:24385): Gtk-WARNING **: cannot open display: :0 derek@vbox:/home$ xhost +access control disabled, clients can connect from any host 2、解压： http://www.cnblogs.com/soul-stone/p/6798716.html 3、安装samba： http://www.cnblogs.com/soul-stone/p/6158442.html 4、安装ssh： http://www.cnblogs.com/soul-stone/p/6158432.html 5、安装java： http://www.cnblogs.com/soul-stone/p/7967930.html 6、git命令行：http://www.cnblogs.com/soul-stone/p/6901214.html 7、shell语法：http://www.cnblogs.com/soul-stone/p/6886130.html 8、GDB命令：http://www.cnblogs.com/soul-stone/p/6131069.html
dpctl 命令实践 dpctl 程序是一个命令行工具用来检测和管理 OpenFlow 数据通路，它能够显示当前的状态数据通路，包括功能配置和表中的条目，以及合适使用 OpenFlow 的内核模块，可以用来添加，删除，修改和监视 datapaths。 查看交换机端口信息基本情况（TCP 端口 6634 是默认交换机监听端口）。 1 2 3 4 5 6 7 8 9 10 # dpctl show tcp:9.123.137.25:6634 features_reply (xid=0x94af8117): ver:0x1, dpid:1 n_tables:255, n_buffers:256 features: capabilities:0xc7, actions:0xfff 1(s1-eth1): addr:2e:d1:ca:aa:af:67, config: 0, state:0 current: 10GB-FD COPPER 2(s1-eth2): addr:66:93:32:1e:9b:9e, config: 0, state:0 current: 10GB-FD COPPER LOCAL(s1): addr:5e:bc:ab:cc:dc:43, config: 0x1, state:0x1 get_config_reply (xid=0x92fc9e48): miss_send_len=0 查看流表信息： 1 2 # dpctl dump-flows tcp:9.123.137.25:6634 stats_reply (xid=0xe2c7ea1e): flags=none type=1(flow) 此时，流表为空，执行 h1 ping h2 无法得到响应。因此我们需要通过 dpctl 手动添加流表项，实现转发。 手动添加流表项： 1 2 3 4 5 6 7 8 # dpctl add-flow tcp:9.123.137.25:6634 in_port=1,actions=output:2 # dpctl add-flow tcp:9.123.137.25:6634 in_port=2,actions=output:1 # dpctl dump-flows tcp:9.123.137.25:6634 stats_reply (xid=0x131ed782): flags=none type=1(flow) cookie=0, duration_sec=13s, duration_nsec=401000000s, table_id=0, priority=32768, \ n_packets=0, n_bytes=0,idle_timeout=60,hard_timeout=0,in_port=1,actions=output:2 cookie=0, duration_sec=5s, duration_nsec=908000000s, table_id=0, priority=32768, \ n_packets=0, n_bytes=0,idle_timeout=60,hard_timeout=0,in_port=2,actions=output:1 此时查看流表可以看到新的转发信息，同时可以在 h1 和 h2 之间可以相互连通。 dpctl 其他常用操作 创建 datapath 编号为 0 1 #dpctl adddp n1:0 增加两个网络设备到新的 datapath 1 2 #dpctl adddp n1:0 eth0 #dpctl adddp n1:0 eth1 检测数据通路接收的流量 1 #dpctl monitor n1:0 在数据通路中删除网络设备 1 #dpctl delif nl:0 eth0
sudo mn --test pingall --topo single,3 //一台交换机，两台主机 sudo mn --test pingall --topo linear,4 //linear表示每台交换机链接一台主机 sudo mn --link tc,bw=10,delay=10ms //带宽设置10M，延迟为10ms sudo mn --mac //mac以1、2递增的顺序保存 sudo mn --switch ovsk --controller ref --topo tree,depth=2,fanout=8 --test pingall //二层八叉树，即九台交换机加上64台主机 sudo mn --topo single,3 --mac --switch ovsk --controller remote // (1)--topo用于指定openflow网络拓扑，MiniNet已经为大多数应用实现了四种类型的openflow网络拓扑：tree，single，linear和minimal。缺省情况下，创建的是minimal拓扑包括四个元素：one OpenFlow kernel switch connected to two hosts, plus the OpenFlowreference controller；而--topo single,3则是1个openflow switch加上3个主机；--topo linear,4 则表示four OpenFlow switches, each switch has one host, and all switchesconnect in a line；--topo tree, depth=2,fanout=8则表示a network with atree topology of depth 2 and fanout 8 (i.e. 9 switches connecting 64 hosts)。 (2)--custom：在上述已有拓扑的基础上，MiniNet支持自定义拓扑，使用一个简单的Python API即可，例如导入自定义的mytoposudo mn --custom ~/mininet/custom/topo-2sw-2host.py --topomytopo --test pingall，详见(http://yuba.stanford.edu/foswiki/bin/view/OpenFlow/MininetWalkthrough)。 (3)--switch：可以有三类openflow交换机：kernel内核状态、user用户态以及ovsk是Open vSwith状态。当然kerner和ovsk的性能和吞吐量会高一些，通过运行sudo mn --switch ovsk --test iperf进行iperf的测试得知。 (4)—controller：可以是参考控制器，NOX或者虚拟机之外的远端控制器，一个指定远端控制器的方法：sudo mn --controller=remote --ip=[controller IP] --port=[controllerlistening port] (5) –mac: 作用是让MAC地址易读，即 setsthe switch MAC and host MAC and IP addrs to small, unique, easy-to-read IDs。 其他一些调试可能用到的命令：Nodes，Net，H2 ping h3，S1 ifconfig等 minet丢包问题：todo
红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的： 它可以在O(log n)时间内做查找，插入和删除，这里的n 是树中元素的数目。 http://blog.csdn.net/npy_lp/article/details/7420689 https://baike.baidu.com/item/%E7%BA%A2%E9%BB%91%E6%A0%91
https://baike.baidu.com/item/%E5%B9%B3%E8%A1%A1%E4%BA%8C%E5%8F%89%E6%A0%91/10421057?fr=aladdin https://www.cnblogs.com/huangxincheng/archive/2012/07/22/2603956.html http://blog.csdn.net/programmingring/article/details/37969745 #include <stdio.h> #include <stdlib.h> /************************************************************************/ /* 平衡二叉树---AVL */ /************************************************************************/ #define LH +1 #define EH 0 #define RH -1 typedef int ElemType; typedef struct BSTNode{ ElemType data; int bf;//balance flag struct BSTNode *lchild,*rchild; }*PBSTree; void R_Rotate(PBSTree* p) { PBSTree lc = (*p)->lchild; (*p)->lchild = lc->rchild; lc->rchild = *p; *p = lc; } void L_Rotate(PBSTree* p) { PBSTree rc = (*p)->rchild; (*p)->rchild = rc->lchild; rc->lchild = *p; *p = rc; } void LeftBalance(PBSTree* T) { PBSTree lc,rd; lc = (*T)->lchild; switch (lc->bf) { case LH: (*T)->bf = lc->bf = EH; R_Rotate(T); break; case RH: rd = lc->rchild; switch(rd->bf) { case LH: (*T)->bf = RH; lc->bf = EH; break; case EH: (*T)->bf = lc->bf = EH; break; case RH: (*T)->bf = EH; lc->bf = LH; break; } rd->bf = EH; L_Rotate(&(*T)->lchild); R_Rotate(T); break; } } void RightBalance(PBSTree* T) { PBSTree lc,rd; lc= (*T)->rchild; switch (lc->bf) { case RH: (*T)->bf = lc->bf = EH; L_Rotate(T); break; case LH: rd = lc->lchild; switch(rd->bf) { case LH: (*T)->bf = EH; lc->bf = RH; break; case EH: (*T)->bf = lc->bf = EH; break; case RH: (*T)->bf = EH; lc->bf = LH; break; } rd->bf = EH; R_Rotate(&(*T)->rchild); L_Rotate(T); break; } } int InsertAVL(PBSTree* T,ElemType e,bool* taller) { if ((*T)==NULL) { (*T)=(PBSTree)malloc(sizeof(BSTNode)); (*T)->bf = EH; (*T)->data = e; (*T)->lchild = NULL; (*T)->rchild = NULL; } else if (e == (*T)->data) { *taller = false; return 0; } else if (e < (*T)->data) { if(!InsertAVL(&(*T)->lchild,e,taller)) return 0; if(*taller) { switch ((*T)->bf) { case LH: LeftBalance(T); *taller = false; break; case EH: (*T)->bf = LH; *taller = true; break; case RH: (*T)->bf = EH; *taller = false; break; } } } else { if(!InsertAVL(&(*T)->rchild,e,taller)) return 0; if (*taller) { switch ((*T)->bf) { case LH: (*T)->bf = EH; *taller = false; break; case EH: (*T)->bf = RH; *taller = true; break; case RH: RightBalance(T); *taller = false; break; } } } return 1; } bool FindNode(PBSTree root,ElemType e,PBSTree* pos) { PBSTree pt = root; (*pos) = NULL; while(pt) { if (pt->data == e) { //找到节点，pos指向该节点并返回true (*pos) = pt; return true; } else if (pt->data>e) { pt = pt->lchild; } else pt = pt->rchild; } return false; } void InorderTra(PBSTree root) { if(root->lchild) InorderTra(root->lchild); printf("%d ",root->data); if(root->rchild) InorderTra(root->rchild); } int main() { int i,nArr[] = {1,23,45,34,98,9,4,35,23}; PBSTree root=NULL,pos; bool taller; for (i=0;i<9;i++) { InsertAVL(&root,nArr[i],&taller); } InorderTra(root); if(FindNode(root,103,&pos)) printf("\n%d\n",pos->data); else printf("\nNot find this Node\n"); return 0; }
作者：知乎用户链接：https://www.zhihu.com/question/19823489/answer/13074347来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。身份证号码中这些数字是怎样排列的，每个数字表示什么意思呢？下面就让我们一起来探索其中的规律吧！新的身份证号码是由18位数字组成的，它们分别表示： （1）前1、2位数字表示：所在省份的代码； （2）第3、4位数字表示：所在城市的代码； （3）第5、6位数字表示：所在区县的代码； （4）第7~14位数字表示：出生年、月、日； （5）第15、16位数字表示：所在地的派出所的代码； （6）第17位数字表示性别：奇数表示男性，偶数表示女性； （7）第18位数字是校检码：也有的说是个人信息码，一般是随计算机的随机产生， 用来检验身份证的正确性。校检码可以是0~9的数字，有时也用x表示。 15位的身份证号 dddddd yymmdd xx p 18位的身份证号 dddddd yyyymmdd xx p y 其中dddddd为地址码（省地县三级）18位中的和15位中的不完全相同 yyyymmdd yymmdd 为出生年月日 xx顺号类编码 p性别 18位中末尾的y为校验码，将前17位的ascii码值经位移、异或运算结果不在0-9的令其为x 18位身份证标准在国家质量技术监督局于1999年7月1日实施的GB11643-1999《公民身份号码》中做了明确规定。 GB11643-1999《公民身份号码》为GB11643-1989《社会保障号码》的修订版，其中指出将原标准名称“社会保障号码”更名为“公民身份号码”，另外GB11643-1999《公民身份号码》从实施之日起代替GB11643-1989。 公民身份号码是特征组合码，由十七位数字本体码和一位校验码组成。排列顺序从左至右依次为：六位数字地址码，八位数字出生日期码，三位数字顺序码和一位校验码。其含义如下： 1. 地址码：表示编码对象常住户口所在县(市、旗、区)的行政区划代码，按GB/T2260的规定执行。 2. 出生日期码：表示编码对象出生的年、月、日，按GB/T7408的规定执行，年、月、日分别用4位、2位、2位数字表示，之间不用分隔符。 3. 顺序码：表示在同一地址码所标识的区域范围内，对同年、同月、同日出生的人编定的顺序号，顺序码的奇数分配给男性，偶数分配给女性。 校验的计算方式： 1. 对前17位数字本体码加权求和 公式为：S = Sum(Ai * Wi), i = 0, ... , 16 其中Ai表示第i位置上的身份证号码数字值，Wi表示第i位置上的加权因子，其各位对应的值依次为： 7 9 10 5 8 4 2 1 6 3 7 9 10 5 8 4 2 2. 以11对计算结果取模 Y = mod(S, 11) 3. 根据模的值得到对应的校验码 对应关系为： Y值： 0 1 2 3 4 5 6 7 8 9 10 校验码：1 0 X 9 8 7 6 5 4 3 2 public class IdentityCard{ int[] weight={7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}; //十七位数字本体码权重 char[] valid={ '1','0','X','9','8','7','6','5','4','3','2'}; //mod11,对应校验码字符值 ///card是除去最后一位前17位的号码 public char getValidateCode(String card){ int sum=0; int mode=0; for(int i=0;i<card.length();i++){ sum=sum+Integer.parseInt(String.valueOf(card.charAt(i)))*weight[i]; } mode=sum%11; return valid[mode]; } }
http://blog.jobbole.com/111629/ 原文出处： Poll的笔记 查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如编译程序中符号表的查找。本文简单概括性的介绍了常见的七种查找算法，说是七种，其实二分查找、插值查找以及斐波那契查找都可以归为一类——插值查找。插值查找和斐波那契查找是在二分查找的基础上的优化查找算法。树表查找和哈希查找会在后续的博文中进行详细介绍。 查找定义：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素（或记录）。 查找算法分类：1）静态查找和动态查找；注：静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。2）无序查找和有序查找。无序查找：被查找数列有序无序均可；有序查找：被查找数列必须为有序数列。 平均查找长度（Average Search Length，ASL）：需和指定key进行比较的关键字的个数的期望值，称为查找算法在查找成功时的平均查找长度。对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL = Pi*Ci的和。Pi：查找表中第i个数据元素的概率。Ci：找到第i个数据元素时已经比较过的次数。 1. 顺序查找 说明：顺序查找适合于存储结构为顺序存储或链接存储的线性表。 查找成功时的平均查找长度为：（假设每个数据元素的概率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ; 当查找不成功时，需要n+1次比较，时间复杂度为O(n); 所以，顺序查找的时间复杂度为O(n)。 C++实现源码： 1 2 3 4 5 6 7 8 9 //顺序查找 int SequenceSearch(int a[], int value, int n) { int i; for(i=0; i<n; i++) if(a[i]==value) return i; return -1; } 2. 二分查找 说明：元素必须是有序的，如果是无序的则要先进行排序操作。 基本思想：也称为是折半查找，属于有序查找算法。用给定值k先与中间结点的关键字比较，中间结点把线形表分成两个子表，若相等则查找成功；若不相等，再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表，这样递归进行，直到查找到或查找结束发现表中没有这样的结点。 复杂度分析：最坏情况下，关键词比较次数为log2(n+1)，且期望时间复杂度为O(log2n)； 注：折半查找的前提条件是需要有序表顺序存储，对于静态查找表，一次排序后不再变化，折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说，维护有序的排序会带来不小的工作量，那就不建议使用。——《大话数据结构》 C++实现源码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 //二分查找（折半查找），版本1 int BinarySearch1(int a[], int value, int n) { int low, high, mid; low = 0; high = n-1; while(low<=high) { mid = (low+high)/2; if(a[mid]==value) return mid; if(a[mid]>value) high = mid-1; if(a[mid]<value) low = mid+1; } return -1; } //二分查找，递归版本 int BinarySearch2(int a[], int value, int low, int high) { int mid = low+(high-low)/2; if(a[mid]==value) return mid; if(a[mid]>value) return BinarySearch2(a, value, low, mid-1); if(a[mid]<value) return BinarySearch2(a, value, mid+1, high); } 3. 插值查找 在介绍插值查找之前，首先考虑一个新问题，为什么上述算法一定要是折半，而不是折四分之一或者折更多呢？ 打个比方，在英文字典里面查“apple”，你下意识翻开字典是翻前面的书页还是后面的书页呢？如果再让你查“zoo”，你又怎么查？很显然，这里你绝对不会是从中间开始查起，而是有一定目的的往前或往后翻。< 同样的，比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5， 我们自然会考虑从数组下标较小的开始查找。 经过以上分析，折半查找这种查找方式，不是自适应的（也就是说是傻瓜式的）。二分查找中查找点计算如下： mid=(low+high)/2, 即mid=low+1/2*(high-low); 通过类比，我们可以将查找的点改进为如下： mid=low+(key-a[low])/(a[high]-a[low])*(high-low)， 也就是将上述的比例参数1/2改进为自适应的，根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数。 基本思想：基于二分查找算法，将查找点的选择改进为自适应选择，可以提高查找效率。当然，差值查找也属于有序查找。 注：对于表长较大，而关键字分布又比较均匀的查找表来说，插值查找算法的平均性能比折半查找要好的多。反之，数组中如果分布非常不均匀，那么插值查找未必是很合适的选择。 复杂度分析：查找成功或者失败的时间复杂度均为O(log2(log2n))。 C++实现源码： 1 2 3 4 5 6 7 8 9 10 11 //插值查找 int InsertionSearch(int a[], int value, int low, int high) { int mid = low+(value-a[low])/(a[high]-a[low])*(high-low); if(a[mid]==value) return mid; if(a[mid]>value) return InsertionSearch(a, value, low, mid-1); if(a[mid]<value) return InsertionSearch(a, value, mid+1, high); } 4. 斐波那契查找 在介绍斐波那契查找算法之前，我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。 黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。 0.618被公认为最具有审美意义的比例数字，这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域，而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。 大家记不记得斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….（从第三个数开始，后边每一个数都是前两个数的和）。然后我们会发现，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。 基本思想：也是二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，提高查找效率。同样地，斐波那契查找也属于一种有序查找算法。 相对于折半查找，一般将待比较的key值与第mid=（low+high）/2位置的元素比较，比较结果分三种情况： 1）相等，mid位置的元素即为所求 2）>，low=mid+1; 3）<，high=mid-1。 斐波那契查找与折半查找很相似，他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1; 开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种 1）相等，mid位置的元素即为所求 2）>，low=mid+1,k-=2; 说明：low=mid+1说明待查找的元素在[mid+1,high]范围内，k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个，所以可以递归的应用斐波那契查找。 3）<，high=mid-1,k-=1。 说明：low=mid+1说明待查找的元素在[low,mid-1]范围内，k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个，所以可以递归 的应用斐波那契查找。 复杂度分析：最坏情况下，时间复杂度为O(log2n)，且其期望复杂度也为O(log2n)。 C++实现源码： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 // 斐波那契查找.cpp#include "stdafx.h" #include <memory> #include <iostream> using namespace std; const int max_size=20;//斐波那契数组的长度 /*构造一个斐波那契数组*/ void Fibonacci(int * F) { F[0]=0; F[1]=1; for(int i=2;i<max_size;++i) F[i]=F[i-1]+F[i-2]; } /*定义斐波那契查找法*/ int FibonacciSearch(int *a, int n, int key) //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字 { int low=0; int high=n-1; int F[max_size]; Fibonacci(F);//构造一个斐波那契数组F int k=0; while(n>F[k]-1)//计算n位于斐波那契数列的位置 ++k; int * temp;//将数组a扩展到F[k]-1的长度 temp=new int [F[k]-1]; memcpy(temp,a,n*sizeof(int)); for(int i=n;i<F[k]-1;++i) temp[i]=a[n-1]; while(low<=high) { int mid=low+F[k-1]-1; if(key<temp[mid]) { high=mid-1; k-=1; } else if(key>temp[mid]) { low=mid+1; k-=2; } else { if(mid<n) return mid; //若相等则说明mid即为查找到的位置 else return n-1; //若mid>=n则说明是扩展的数值,返回n-1 } } delete [] temp; return -1; } int main() { int a[] = {0,16,24,35,47,59,62,73,88,99}; int key=100; int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key); cout<<key<<" is located at:"<<index; return 0; } 5. 树表查找 5.1 最简单的树表查找算法——二叉树查找算法。 基本思想：二叉查找树是先对待查找的数据进行生成树，确保树的左分支的值小于右分支的值，然后在就行和每个节点的父节点比较大小，查找最适合的范围。 这个算法的查找效率很高，但是如果使用这种查找方法要首先创建树。 二叉查找树（BinarySearch Tree，也叫二叉搜索树，或称二叉排序树Binary Sort Tree）或者是一棵空树，或者是具有下列性质的二叉树： 1）若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2）若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3）任意节点的左、右子树也分别为二叉查找树。 二叉查找树性质：对二叉查找树进行中序遍历，即可得到有序的数列。 不同形态的二叉查找树如下图所示： 有关二叉查找树的查找、插入、删除等操作的详细讲解，请移步浅谈算法和数据结构: 七 二叉查找树。 复杂度分析：它和二分查找一样，插入和查找的时间复杂度均为O(logn)，但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候，树没有保持平衡（比如，我们查找上图（b）中的“93”，我们需要进行n次查找操作）。我们追求的是在最坏的情况下仍然有较好的时间复杂度，这就是平衡查找树设计的初衷。 下图为二叉树查找和顺序查找以及二分查找性能的对比图： 基于二叉查找树进行优化，进而可以得到其他的树表查找算法，如平衡树、红黑树等高效算法。 5.2 平衡查找树之2-3查找树（2-3 Tree） 2-3查找树定义：和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下： 1）要么为空，要么： 2）对于2节点，该节点保存一个key及对应value，以及两个指向左右节点的节点，左节点也是一个2-3节点，所有的值都比key要小，右节点也是一个2-3节点，所有的值比key要大。 3）对于3节点，该节点保存两个key及对应value，以及三个指向左中右的节点。左节点也是一个2-3节点，所有的值均比两个key中的最小的key还要小；中间节点也是一个2-3节点，中间节点的key值在两个跟节点key值之间；右节点也是一个2-3节点，节点的所有key值比两个key中的最大的key还要大。 2-3查找树的性质： 1）如果中序遍历2-3查找树，就可以得到排好序的序列； 2）在一个完全平衡的2-3查找树中，根节点到每一个为空节点的距离都相同。（这也是平衡树中“平衡”一词的概念，根节点到叶节点的最长距离对应于查找算法的最坏情况，而平衡树中根节点到叶节点的距离都一样，最坏情况也具有对数复杂度。） 性质2）如下图所示： 复杂度分析： 2-3树的查找效率与树的高度是息息相关的。 在最坏的情况下，也就是所有的节点都是2-node节点，查找效率为lgN 在最好的情况下，所有的节点都是3-node节点，查找效率为log3N约等于0.631lgN 距离来说，对于1百万个节点的2-3树，树的高度为12-20之间，对于10亿个节点的2-3树，树的高度为18-30之间。 对于插入来说，只需要常数次操作即可完成，因为他只需要修改与该节点关联的节点即可，不需要检查其他节点，所以效率和查找类似。下面是2-3查找树的效率： 5.3 平衡查找树之红黑树（Red-Black Tree） 2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgn，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。 基本思想：红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。 红黑树的定义： 红黑树是一种具有红色和黑色链接的平衡查找树，同时满足： 红色节点向左倾斜 一个节点不可能有两个红色链接 整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。 下图可以看到红黑树其实是2-3树的另外一种表现形式：如果我们将红色的连线水平绘制，那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。 红黑树的性质：整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同（2-3树的第2）性质，从根节点到叶子节点的距离都相等）。 复杂度分析：最坏的情况就是，红黑树中除了最左侧路径全部是由3-node节点组成，即红黑相间的路径长度是全黑路径长度的2倍。 下图是一个典型的红黑树，从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍： 红黑树的平均高度大约为logn。 下图是红黑树在各种情况下的时间复杂度，可以看出红黑树是2-3查找树的一种实现，它能保证最坏情况下仍然具有对数的时间复杂度。 红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现，如： Java中的java.util.TreeMap,java.util.TreeSet； C++ STL中的：map,multimap,multiset； .NET中的：SortedDictionary,SortedSet 等。 5.4 B树和B+树（B Tree/B+ Tree） 平衡查找树中的2-3树以及其实现红黑树。2-3树种，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。 维基百科对B树的定义为“在计算机科学中，B树（B-tree）是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。 B树定义： B树可以看作是对2-3查找树的一种扩展，即他允许每个节点有M-1个子节点。 根节点至少有两个子节点 每个节点有M-1个key，并且以升序排列 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间 其它节点至少有M/2个子节点 下图是一个M=4 阶的B树: 可以看到B树是2-3树的一种扩展，他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似，这里就不介绍了。下面是往B树中依次插入 6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4 的演示动画： B+树定义： B+树是对B树的一种变形树，它与B树的差异在于： 有k个子结点的结点必然有k个关键码； 非叶结点仅具有索引作用，跟记录有关的信息均存放在叶结点中。 树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。 如下图，是一个B+树: 下图是B+树的插入动画： B和B+树的区别在于，B+树的非叶子结点只包含导航信息，不包含实际的值，所有的叶子结点和相连的节点使用链表相连，便于区间查找和遍历。 B+ 树的优点在于： 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。 B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。 但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。 下面是B 树和B+树的区别图： B/B+树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如： Windows：HPFS文件系统； Mac：HFS，HFS+文件系统； Linux：ResiserFS，XFS，Ext3FS，JFS文件系统； 数据库：ORACLE，MYSQL，SQLSERVER等中。 有关B/B+树在数据库索引中的应用，请看张洋的《MySQL索引背后的数据结构及算法原理》这篇文章，这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍，推荐阅读。 树表查找总结： 二叉查找树平均查找性能不错，为O(logn)，但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化，我们可以使用平衡查找树。平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树，应用非常广泛，很多编程语言的内部实现都或多或少的采用了红黑树。 除此之外，2-3查找树的另一个扩展——B/B+平衡树，在文件系统和数据库系统中有着广泛的应用。 6. 分块查找 分块查找又称索引顺序查找，它是顺序查找的一种改进方法。 算法思想：将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，…… 算法流程：step1 先选取各块中的最大关键字构成一个索引表；step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。 7. 哈希查找 什么是哈希表（Hash）？ 我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数， 也叫做散列函数），使得每个元素的关键字都与一个函数值（即数组下标）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每一个元素”分类”，然后将这个元素存储在相应”类”所对应的地方。但是，不能够保证每个元素的关键字与函数值是一一对应的，因此极有可能出现对于不同的元素，却计算出了相同的函数值，这样就产生了”冲突”，换句话说，就是把不同的元素分在了相同的”类”之中。后面我们将看到一种解决”冲突”的简便做法。 总的来说，”直接定址”与”解决冲突”是哈希表的两大特点。 什么是哈希函数？ 哈希函数的规则是：通过某种转换关系，使关键字适度的分散到指定大小的的顺序结构中，越分散，则以后查找的时间复杂度越小，空间复杂度越高。 算法思想：哈希的思路很简单，如果所有的键都是整数，那么就可以使用一个简单的无序数组来实现：将键作为索引，值即为其对应的值，这样就可以快速访问任意键的值。这是对于简单的键的情况，我们将其扩展到可以处理更加复杂的类型的键。 算法流程：1）用给定的哈希函数构造哈希表； 2）根据选择的冲突处理方法解决地址冲突； （常见的解决冲突的方法：拉链法和线性探测法。详细的介绍可以参见：浅谈算法和数据结构: 十一 哈希表。） 3）在哈希表的基础上执行哈希查找。 哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制，那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1)；如果没有时间限制，那么我们可以使用无序数组并进行顺序查找，这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。 复杂度分析： 单纯论查找复杂度：对于无冲突的Hash表而言，查找复杂度为O(1)（注意，在查找之前我们需要构建相应的Hash表）。 使用Hash，我们付出了什么？我们在实际编程中存储一个大规模的数据，最先想到的存储结构可能就是map，也就是我们常说的KV pair，经常使用Python的博友可能更有这种体会。使用map的好处就是，我们在后续处理数据处理时，可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表，那我们在获取了超高查找效率的基础上，我们付出了什么？ Hash是一种典型以空间换时间的算法，比如原来一个长度为100的数组，对其查找，只需要遍历且匹配相应记录即可，从空间复杂度上来看，假如数组存储的是byte类型数据，那么该数组占用100byte空间。现在我们采用Hash算法，我们前面说的Hash必须有一个规则，约束键与存储位置的关系，那么就需要一个固定长度的hash表，此时，仍然是100byte的数组，假设我们需要的100byte用来记录键与位置的关系，那么总的空间为200byte,而且用于记录规则的表大小会根据规则，大小可能是不定的。 Hash算法和其他查找算法的性能对比：
/* linux-2.6.38.8/include/linux/compiler-gcc4.h */ #define __compiler_offsetof(a,b) __builtin_offsetof(a,b) /* linux-2.6.38.8/include/linux/stddef.h */ #undef offsetof #ifdef __compiler_offsetof #define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER) #else #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) #endif /* linux-2.6.38.8/include/linux/kernel.h * * container_of - cast a member of a structure out to the containing structure * @ptr: the pointer to the member. * @type: the type of the container struct this is embedded in. * @member: the name of the member within the struct. * */ #define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)->member ) *__mptr = (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );}) #include <stdio.h> struct test_struct { int num; char ch; float fl; }; int main(void) { struct test_struct init_test_struct = { 99, 'C', 59.12 }; char *char_ptr = &init_test_struct.ch; struct test_struct *test_struct = container_of(char_ptr, struct test_struct, ch); printf(" test_struct->num = %d\n test_struct->ch = %c\n test_struct->fl = %f\n", test_struct->num, test_struct->ch, test_struct->fl); return 0; }
http://www.onie.org/ https://github.com/opencomputeproject/onie
https://www.cnblogs.com/ilinuxer/p/6364064.html https://www.cnblogs.com/ggjucheng/archive/2012/08/19/2646466.html
发表了文章
2016-12-04
发表了文章
2016-12-04
发表了文章
2016-12-04
发表了文章
2016-12-04
发表了文章
2016-12-04
发表了文章
2016-12-10
发表了文章
2016-12-10
发表了文章
2016-12-10
发表了文章
2017-01-24
发表了文章
2017-02-05
发表了文章
2017-02-07
发表了文章
2017-02-07
发表了文章
2017-02-09
发表了文章
2017-02-09
发表了文章
2017-02-09
发表了文章
2017-02-11
发表了文章
2017-02-19
发表了文章
2017-04-02
发表了文章
2017-04-02
发表了文章
2017-04-02
